Binary tree (thoughts)

Undertaking Binary tree （ Programme ）, First, I will repeat the general outline of binary tree problem solving summarized in the previous article ：

1. Whether you can get the answer by traversing the binary tree ？ If possible , Use one traverse With external variables , This is called 「 Traverse 」 The mode of thinking .
2. Whether a recursive function can be defined , Pass the subproblem （ subtree ） The answer to the original question ？ If possible , Write the definition of this recursive function , And make full use of the return value of this function , This is called 「 Break down the problem 」 The mode of thinking .

No matter which mode of thinking you use , You need to think ：

If you extract a binary tree node separately , What does it need to do ？ When do I need to （ front / in / Post sequence position ） do ？ You don't have to worry about other nodes , Recursive functions will help you perform the same operation on all nodes .

This article takes several simple topics as examples , Let me show you how to apply these general principles , understand 「 Traverse 」 Thinking and 「 Break down the problem 」 What are the differences and connections between the thinking of .

One 、 Flip binary tree

Force to buckle 226 topic 「 Flip binary tree 」

It's not hard to find out , As long as the left and right child nodes of each node on the binary tree are exchanged , The final result is a completely flipped binary tree .

So now I begin to meditate on the general outline of binary tree problem solving ：

1、 Can this question be used 「 Traverse 」 Thinking mode to solve ？

Sure , I write one. traverse Function traverses each node , Just turn the left and right child nodes of each node upside down .

Pull out a single node , What does it need to do ？ Let it swap its left and right child nodes .

When do you need to do ？ It seems that the first, middle and last positions are OK .

Sum up , You can write the following solution code ：

//  The main function 
TreeNode invertTree(TreeNode root) {
    
    //  Traversing the binary tree , Swap the children of each node 
    traverse(root);
    return root;
}

//  Binary tree traversal function 
void traverse(TreeNode root) {
    
    if (root == null) {
    
        return;
    }

    /****  Preamble position  ****/
    //  What each node needs to do is exchange its left and right child nodes 
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    //  Ergodic framework , To traverse the nodes of the left and right subtrees 
    traverse(root.left);
    traverse(root.right);
}

2、 Can this question be used 「 Break down the problem 」 Thinking mode to solve ？

We try to give invertTree Function gives a definition ：

//  Definition ： Will be with  root  Flip the root of this binary tree , Returns the root node of the flipped binary tree 
TreeNode invertTree(TreeNode root);

And think about it , For a binary tree node x perform invertTree(x), You can do something with the definition of this recursive function ？

I can use invertTree(x.left) The first x The left subtree of is flipped , Reuse invertTree(x.right) hold x The right subtree of is flipped , Finally, put x The left and right subtrees of , This happens to be done with x The flip of a whole binary tree with roots , That's it invertTree(x) The definition of .

Write the solution code directly ：

//  Definition ： Will be with  root  Flip the root of this binary tree , Returns the root node of the flipped binary tree 
TreeNode invertTree(TreeNode root) {
    
    if (root == null) {
    
        return null;
    }
    //  Use functions to define , First flip the left and right subtrees 
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    //  Then swap the left and right child nodes 
    root.left = right;
    root.right = left;

    //  And define logical self-sufficiency ： With  root  The binary tree with roots has been flipped , return  root
    return root;
}

such 「 Break down the problem 」 The idea of , The core is that you have to give a proper definition of recursive functions , Then explain your code with the definition of the function ; If your logic succeeds, it's right , Then it shows that your algorithm is correct .

The second question is 、 Fill the right pointer of the node

Force to buckle 116 topic 「 Fill in the right pointer of each binary tree node 」

How to do this problem ？ Let's meditate on the general outline of binary tree problem solving ：

1、 Can this question be used 「 Traverse 」 Thinking mode to solve ？

Conventional traverse Function is to traverse all nodes of a binary tree , But what we want to traverse now is Between two adjacent nodes 「 Gap 」.
So we can abstract on the basis of binary tree , You see each box in the diagram as a node ：

such , A binary tree is abstracted into a trident tree , Each node in the Trident tree is the two adjacent nodes of the original binary tree .

//  The main function 
Node connect(Node root) {
    
    if (root == null) return null;
    //  Traverse 「 Trident tree 」, Connect adjacent nodes 
    traverse(root.left, root.right);
    return root;
}

//  Trident tree traversal framework 
void traverse(Node node1, Node node2) {
    
    if (node1 == null || node2 == null) {
    
        return;
    }
    /****  Preamble position  ****/
    //  Put the two incoming nodes together 
    node1.next = node2;
    
    //  Connect two children of the same parent node 
    traverse(node1.left, node1.right);
    traverse(node2.left, node2.right);
    //  Connect two child nodes that span the parent node 
    traverse(node1.right, node2.left);
}

2、 Can this question be used 「 Break down the problem 」 Thinking mode to solve ？
There seems to be no particularly good idea , So this question cannot be used 「 Break down the problem 」 To solve .

3、 Of course, you can also use the usual hierarchical traversal method to solve

class Solution {
    
    public Node connect(Node root) {
    
        if(root==null) return null;
        Deque<Node> q=new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()){
    
            int size=q.size();
            Node pre=q.pop();
            if(pre.left!=null) q.offer(pre.left);
            if(pre.right!=null) q.offer(pre.right);
            for(int i=0;i<size-1;i++){
    
                Node cur=q.pop();
                pre.next=cur;
                pre=cur;
                if(pre.left!=null) q.offer(pre.left);
                if(pre.right!=null) q.offer(pre.right);
            }
            pre.next=null;
        }
        return root;
    }
}

Third question 、 Expand a binary tree into a linked list

Force to buckle 114 topic 「 Expand a binary tree into a linked list 」

1、 Can this question be used 「 Traverse 」 Thinking mode to solve ？

Sure , But we need to create a new linked list , But the return value of the function is viod, Show that the problem requires us to operate in situ

2、 Can this question be used 「 Break down the problem 」 Thinking mode to solve ？
We try to give the definition of a function ：

//  Definition ： Input node  root, then  root  The binary tree for the root will be flattened into a linked list 
void flatten(TreeNode root);

With this function definition , How to pull a tree into a linked list according to the title requirements ？

For a node x, You can perform the following process ：

1、 First use of flatten(x.left) and flatten(x.right) take x The left and right branches of the tree are flattened .

2、 take x The right subtree is connected to the bottom of the left subtree , Then take the entire left subtree as the right subtree .

Look directly at the code implementation ：

//  Definition ： Will be with  root  Flatten the root tree into a linked list 
void flatten(TreeNode root) {
    
    // base case
    if (root == null) return;
    
    //  Using definitions , Flatten the left and right subtrees 
    flatten(root.left);
    flatten(root.right);

    /****  Postorder traversal position  ****/
    // 1、 The left and right subtrees have been flattened into a linked list 
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // 2、 Take the left subtree as the right 
    root.left = null;
    root.right = left;

    // 3、 Connect the original right subtree to the end of the current right subtree 
    TreeNode p = root;
    while (p.right != null) {
    
        p = p.right;
    }
    p.right = right;

}

You see , That's the charm of recursion , You say? flatten How does the function flatten the left and right subtrees ？

It's not easy to make it clear , But as long as you know flatten And use this definition , Let each node do what it should do , then flatten The function will work as defined .