Java solution with in-order traversal


  • 2
    A
    public void recoverTree(TreeNode root) {
        if (root == null)
            return;
        Stack<TreeNode> stack = new Stack<TreeNode> ();
        List<TreeNode> violates = new ArrayList<TreeNode> ();
        TreeNode pre = null;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else{
                cur = stack.pop();
                if (pre != null && cur.val < pre.val) {
                    if (violates.size() == 0) {
                        violates.add(pre);
                        violates.add(cur);
                    } else{
                        violates.set(1, cur);
                    }
                }
                pre = cur;
                cur = cur.right;
            }
        }
        if (violates.size() != 0) {
            int temp = violates.get(0).val;
            violates.get(0).val = violates.get(1).val;
            violates.get(1).val = temp;
        }
    }

  • 0
    A

    Given that a stack is used, is it really O(1) space?


  • 0
    A

    Thanks for reminding me. Yes! It should be O(tree's height).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.