Subject to introduce

Force buckle 99 questions: leetcode-cn.com/problems/re…

Methods a

We need to consider what happens to the original binary search tree when two nodes are swapped incorrectly. For a binary search tree, we know that if we perform a middle-order traversal, the resulting value sequence is incrementally ordered, and if we swap two nodes incorrectly, it is equivalent to swapping two values in this value sequence, which breaks the incrementally increasing value sequence.

Let’s look at what happens if you swap two values in an increasing sequence. Suppose there is an increasing sequence a=[1,2,3,4,5,6,7]a=[1,2,3,4,5,6,7]. If we swap two non-adjacent numbers, such as 22 and 66, and the original sequence becomes a=[1,6,3,4,5,2,7] A =[1,6,3,4,5,2,7], then it is clear that there are two positions in the sequence that do not satisfy a[I] < a[I +1]. In this sequence, it is 6>36>3. 5>25>2, so as long as we find these two positions, we can find the two nodes that were swapped incorrectly.

At this point, the solution has been revealed:

    1. Find the position in the binary search tree where the sequence of values obtained by sequential traversal does not meet the condition.
    1. Just swap the values of these two nodes.

The code is as follows:

class Solution {
    public void recoverTree(TreeNode root) {
        List<Integer> nums = new ArrayList<Integer>();
        inorder(root, nums);
        int[] swapped = findTwoSwapped(nums);
        recover(root, 2, swapped[0], swapped[1]);
    }

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

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

    public void recover(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; } } recover(root.right, count, x, y); recover(root.left, count, x, y); }}}Copy the code

Complexity analysis

  • Time complexity: O(N), where NN is the number of nodes in the binary search tree. The middle-order traversal requires O(N) time, and the two switching nodes are judged to be O(1) in the best case and O(N) in the worst case, so the total time complexity is O(N).
  • Space complexity: O(N). We need a NUMS array to store the tree’s middle-order traversal list.

Method 2

The space complexity of method 1 is relatively high. In fact, it is not so troublesome to find the two nodes that need to be swapped. According to the analysis of the problem, we only need to traverse the middle order to find the first ascending order abnormal maximum node and the last ascending order abnormal minimum node. Then swap the two nodes val.

The code is as follows:

class Solution {
    // The first maximum node
    TreeNode firstMax=null;
	// The last minimum node
    TreeNode lastMin=null;
	// The previous node
    TreeNode prev=new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root){
        helper(root);
        if(firstMax! =null&& lastMin! =null) {inttmp=firstMax.val; firstMax.val=lastMin.val; lastMin.val=tmp; }}public void helper(TreeNode root){
        if(null==root)return;
        helper(root.left);
        if(root.val<prev.val) {
            lastMin=root;
            if(firstMax==null)firstMax=prev; } prev=root; helper(root.right); }}Copy the code

Complexity analysis

  • Time complexity: O(N).
  • Space complexity: O(H), where H is the height of the binary tree.