IncreaseOrderTree897

[underwindfall]

• https://leetcode-cn.com/problems/increasing-order-search-tree/

• 思路

  • inOrder
  • stack

• 刷15mins

• 刷5mins

  // time O(N)
    // space O(N)
    TreeNode curr;
    public TreeNode increasingBST(TreeNode root) {
       TreeNode ans = new TreeNode(0);
       curr = ans;
       inOrder(root);
       return ans.right;
    }
    
    
    
    void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        node.left = null;
        curr.right = node;
        curr = node;
        inOrder(node.right);
    }

    // time O(N)
    // space O(N)
    public TreeNode increasingBSTStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return root;
        }
        TreeNode curr = root;
        TreeNode prev = null;
        TreeNode newRoot = null;
        while (!stack.isEmpty() || curr != null) {
            // keep going left, util you hit a null
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            // pop from the stack and create the new root if not already created
            curr = stack.pop();
            if (newRoot == null) {
                newRoot = curr;
            }

            // assign the current element to previous element's right
            if (prev != null) {
                prev.right = curr;
                curr.left = null;
            }
            // point prev to cur and move curr to right
            prev = curr;
            curr = curr.right;
        }
        return newRoot;
    }