DLL ro BST BST to DLL

已写bst to dll

class Test{
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    static class TreeNode {
      public int val;
      public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }
    }

    public static TreeNode bstToDoublyList(TreeNode root) {  
        TreeNode dummy = new TreeNode(0);
        TreeNode prev = dummy;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curt = root;
        while (curt != null){
            stack.push(curt);
            curt = curt.left;
        }
        while (!stack.isEmpty()){
            curt = stack.pop();
            prev.right = curt;
            curt.left = prev;
            prev = curt;
            curt = curt.right;
            while (curt != null){
                stack.push(curt);
                curt = curt.left;
            }
        }
        // if circular, add:
        // prev.right = dummy.right;
        // dummy.right.left = prev;
        return dummy.right;
    }

    static void printList(TreeNode node) 
    {
        while (node != null) 
        {
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
  
    /* Driver program to test above functions*/
    public static void main(String[] args) 
    {

       //      20
       //    /   \
       //   15    30
       //  / \   / 
       // 10 18  25 
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(15);
        root.right = new TreeNode(30);
        root.left.left = new TreeNode(10);
        root.left.right = new TreeNode(18);
        root.right.left = new TreeNode(25);
  
        // Convert to DLL
        TreeNode head = bstToDoublyList(root);
  
        // Print the converted list
        printList(head);
    }
}

dll to bst

//convert sorted array to BST time O(n) space o(n) stack space o(nlogn)
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0){
            return null;
        }        
        return helper(nums, 0, nums.length - 1);
    }
    
    private TreeNode helper(int[] nums, int left, int right){
        if (left > right){
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}


//109.Convert Sorted List to Binary Search Tree  time: O(nLogn)
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null){
            return null;
        }
        return toBST(head, null);
    }
    
    private TreeNode toBST(ListNode head, ListNode tail){
        if (head == tail){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = toBST(head, slow);
        root.right = toBST(slow.next, tail);
        return root;
    }
}

//inplace (using original DLL and don't creat new TreeNode)convert (circular) doubly linkedlist to balanced bst, O(n) time, O(logn) space
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    private ListNode curr;
    
    public ListNode sortedListToBST(ListNode head) {
        if (head == null) {
            return head;
        }
        // 1.if it's a circular list that tail connects to head
        // curr.prev.next = null;
        // curr.prev = null;
        // 2.if it's a circular list that tail connects to any node
        // ListNode tail = getTail(head);
        // tail.next.prev = null;
        // tail.next = null;
        // after cutting the cycle, we can count nodes and build trees
        curr = head;
        int size = getSize(head);
        return buildTree(size);
    }
    
    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
    
    private ListNode buildTree(int size) {
        if (size <= 0) {
            return null;
        }
        ListNode left = buildTree(size / 2);
        ListNode root = curr;//curr is the root of these two subtrees
        curr = curr.next;
        ListNode right = buildTree(size - 1 - size / 2);
        root.prev = left;
        root.next = right;
        return root;
    }
    
    //this method is almost same as Linked List Cycle 2
    public ListNode getTail(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return slow;//return the tail
    }
}