Leetcode-99. restore binary search tree

subject

Give you the root node of the binary search tree root , In the tree just The values of the two nodes are incorrectly exchanged . Please... Without changing its structure , Restore the tree .

Example 1：

Input ：root = [1,3,null,null,2]
Output ：[3,1,null,null,2]
explain ：3 It can't be 1 The left child , because 3 > 1 . In exchange for 1 and 3 Make the binary search tree efficient .
Example 2：

Input ：root = [3,1,4,null,null,2]
Output ：[2,1,4,null,null,3]
explain ：2 Can't be in 3 In the right subtree , because 2 < 3 . In exchange for 2 and 3 Make the binary search tree efficient .

Tips ：

The number of nodes on the tree is in the range [2, 1000] Inside
-231 <= Node.val <= 231 - 1

Advanced ： Use O(n) The solution of space complexity is easy to realize . You can think of one that only uses O(1) Space solutions ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/recover-binary-search-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

package org.lht.boot.lang. Algorithm .leetcode;

import java.util.ArrayList;
import java.util.List;

/** * Description: https://leetcode.cn/problems/recover-binary-search-tree/ * * @Author lht * @Date 2022/7/13 21:00 **/
public class L99 Restore binary search tree  {
    


    public static void main(String[] args) {
    
        TreeNode root = new TreeNode();
        //.. Defining parameters 
        recoverTree(root);
    }

    /** *  transformation  * @param root */
    public static void recoverTree(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int[] index = findIndex(list);
        recoverTree(root, 2, index[0], index[1]);

    }

    /** *  According to the result of middle order traversal , Find the two exchanged node values . * @param nums * @return */
    public static int[] findIndex(List<Integer> nums) {
    
        int preIndex = -1;
        int nextIndex = -1;
        for (int i = 0; i < nums.size() - 1; i++) {
    
            if (nums.get(i) > nums.get(i + 1)) {
    
                preIndex = i + 1;
                if (nextIndex == -1) {
    
                    nextIndex = i;
                } else {
    
                    break;
                }
            }
        }
        int x = nums.get(preIndex), y = nums.get(nextIndex);
        return new int[]{
    x, y};
    }


    /** *  Exchange the two found nodes , Exchange come here  * @param root * @param count * @param x * @param y */
    public static void recoverTree(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;
                }
            }
            recoverTree(root.left, count, x, y);
            recoverTree(root.right, count, x, y);
        }
    }

    /** *  In the sequence traversal  * * @param root * @param nums */
    public static void inorder(TreeNode root, List<Integer> nums) {
    
        if (root == null) {
    
            return;
        }
        inorder(root.left, nums);
        nums.add(root.val);
        inorder(root.right, nums);
    }


}

Their thinking

This question is actually very simple , There are several ideas

First of all , The result of traversal using middle order is ordered .

second , The two nodes in the binary search tree are exchanged , The structure of the tree has not changed

Third , And only two nodes are exchanged , So you can find two swapped nodes .

Fourth , Switching nodes , Do not operate on tree results , Therefore, any kind of traversal can be used .

take 7 and 4 In exchange .