RecoverTree99

[underwindfall]

• https://leetcode-cn.com/problems/recover-binary-search-tree/

• 思路

  • inorder dfs

• 刷15mins

• 刷5mins

  // time O(n)
    // space O(h)
    class InoderImplict {
        public void recoverTree(TreeNode root) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode x = null, y = null, pred = null;
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (pred != null && root.val < pred.val) {
                    y = root;
                    if (x == null) {
                        x = pred;
                    } else {
                        break;
                    }
                }
                pred = root;
                root = root.right;
            }
            swap(x, y);
        }

        void swap(TreeNode x, TreeNode y) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    // time O(n)
    // space O(n)
    class InOrderExplict {
        List<Integer> nums = new ArrayList<>();

        public void recoverTree(TreeNode root) {
            // left mid right
            inOrder(root, nums);
            int[] swapped = findTwoSwapped(nums);
            restore(root, 2, swapped[0], swapped[1]);
        }

        void inOrder(TreeNode root, List<Integer> nums) {
            if (root == null) {
                return;
            }
            inOrder(root.left, nums);
            nums.add(root.val);
            inOrder(root.right, nums);
        }

        int[] findTwoSwapped(List<Integer> nums) {
            int n = nums.size();
            int index1 = -1, index2 = -1;
            for (int i = 0; i < n - 1; ++i) {
                if (nums.get(i + 1) < nums.get(i)) {
                    index2 = i + 1;
                    if (index1 == -1) {
                        index1 = i;
                    } else {
                        break;
                    }
                }
            }
            int x = nums.get(index1), y = nums.get(index2);
            return new int[] { x, y };
        }

        void restore(TreeNode root, int count, int x, int y) {
            if (root != null) {
                if (root.val == x || root.val == y) {
                    root.val = root.val == x ? y : x;
                    if (--count == 0) {
                        return;
                    }
                }
                restore(root.right, count, x, y);
                restore(root.left, count, x, y);
            }
        }
    }