Restore the binary search tree [simulate according to the meaning of the question - > find the problem - > analyze the problem - > see the bidding]

Preface

Too many algorithm questions , Knowledge points have also accumulated , At this time, we need to see what we can do , Flexible combination of knowledge points . But I want to make a move , You have to know what the topic is about , If you can't find out what the trick is , How to talk about defying tactics ？
General process of problem solving ： According to the meaning of the question, simulate and understand -> Find the problem -> To analyze problems ( Sorting )-> See following .

One 、 Restore binary search tree

Two 、 See following

package everyday.medium;

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

//  Restore binary search tree 
public class RecoverTree {
    
    /* target： There are two nodes that do not satisfy the size relationship , Exchange it .  I haven't analyzed the subject before , Only simple traversal , Find a situation that varies from front to back , Just swap it , As it says target.  summary ： I didn't settle down to analyze the problem , Fully understand the topic , So as to open the right path of analysis , Don't pay attention to details , The direction cannot be opened .  The analysis is as follows ,  Exchange two elements , This will result in two decrements in the medium order increasing sequence , Set the first place a > b; The second place  c > d; Put the smallest d And the biggest a In exchange for , The sequence becomes incremented .  Of course , If it is two adjacent , There is only one difference , set up a > b, Put the smallest b And the biggest a In exchange for , The sequence becomes incremented .  Record decreasing 4/2 Nodes , Exchange according to the situation . */

    public void recoverTree(TreeNode root) {
    
        //  In the sequence traversal , Looking for diminishing 4/2 Nodes , Put in list In .
        inOrder(root);
        //  Deal with the exchange according to the situation .
        //  Let what needs to be exchanged be x and y
        TreeNode x = error.get(0), y = error.size() == 2 ? error.get(1) : error.get(3);
        //  In exchange for x  and  y The value of the can , No need to change the structure .
        // swap
        int t = x.val;
        x.val = y.val;
        y.val = t;
    }

    List<TreeNode> error = new ArrayList<>();
    TreeNode pre = null;

    private void inOrder(TreeNode root) {
    
        //  Reach empty node , End recursion .
        if (root == null) return;
        //  Traverse left subtree 
        inOrder(root.left);
        //  In the sequence traversal .
        if (pre != null && pre.val > root.val) {
    
            error.add(pre);
            error.add(root);
        }
        //  Update forerunner .
        pre = root;
        //  Traversal right subtree .
        inOrder(root.right);
    }

    // Definition for a binary tree node.
    public class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
    
        }

        TreeNode(int val) {
    
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
    
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

summary

1） Restore binary tree , Why do wrong binary trees appear ？ Ask key questions .
2） General process of problem solving ： According to the meaning of the question, simulate and understand -> Find the problem -> To analyze problems ( Sorting )-> See following .

reference

[1] LeetCode Restore binary search tree