Some recursive and iterative problem solving ideas of binary tree (clear and easy to understand)

Catalog

One . recursive

（1）. Traversal in front, middle and back order

（2）. Classical recursive solution

（1） For example, judge whether a tree is a balanced binary tree

（2） Merge two binary trees into a binary tree

Two . iteration （ Sequence traversal ）

（1）. Normal sequence traversal

（2）. Layered sequence traversal

（3）. With depth （depth） And serial number （pos） Sequence traversal of

---

One . recursive

（1）. Traversal in front, middle and back order

The essence is the same , The main reason is that the current traversal node is processed in different ways .

The method of traversal before, during and after the sequence can refer to my other blog

https://blog.csdn.net/qq_24016309/article/details/122382593

---

（2）. Classical recursive solution

（1） For example, judge whether a tree is a balanced binary tree

Given a binary tree , Determine whether the binary tree is a balanced binary tree . For standard LeetCode The first 110 topic

Ideas ： Whether a tree is a balanced binary tree ,

1. First, judge whether the left subtree of the tree is a balanced binary tree
2. Then judge whether the right subtree of the tree is a balanced binary tree
3. Judge whether the current height difference between the left and right subtrees > 1

If you write recursion directly, there will be many repeated operations when calculating the height of the tree .

ps: Optimal solution ： Start with the function of tree height , If the left and right subtrees have one -1 Just go back to -1, Height difference >1 Also returned -1. Then we can find the height of the tree directly , If the tree height is not -1, That's the balanced binary tree . This method finds the function with repeated operation , And the targeted optimization of this function is worth noting .

（2） Merge two binary trees into a binary tree

The rule for merging is if two nodes overlap , Then add their values as the new values after node merging , Otherwise, no NULL The node of will be the node of the new binary tree directly . For standard LeetCode The first 617 topic

Ideas ： To merge two binary trees ,

1. First, if one of the two incoming trees is empty , Then just go back to another tree
2. If neither tree is empty , It would be new A new root node , The value is equal to the sum of the values of the root nodes of the two trees
3. then node.left=merge( Of the first tree left, Of the second tree left);node.right = merge( Of the first tree right, Of the second tree right)

---

Two . iteration （ Sequence traversal ）

（1）. Normal sequence traversal

Using the queue , Sequence traversal

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
    TreeNode node = queue.remove();
    System.out.println(node);
    if (node.left != null){
        queue.add(node.left);
    }
    if (node.right != null){
        queue.add(node.right);
    }
}

---

（2）. Layered sequence traversal

If we want to traverse the sequence layer by layer , Then you can use the queue size function , Before the start of each cycle , Get the length of the current queue first , That is, the number of nodes in the current layer , Then go to another while loop , loop size Just turn . For standard LeetCode The first 102 topic （ It is required to put the elements of each layer into different list Collection ）.

while (!queue.isEmpty()){
    int size = queue.size();
    List<Integer> listEle = new ArrayList<>();
    while (size > 0){
        TreeNode node = queue.remove();
        if (node.left != null){
            queue.add(node.left);
        }
        if (node.right != null){
            queue.add(node.right);
        }
        listEle.add(node.val);
        size--;
    }
    list.add(listEle);
}

---

（3）. With depth （depth） And serial number （pos） Sequence traversal of

Define one for yourself MyNode, It stores a depth （depth） And serial number （pos）, It is used to represent the serial number of the current node , Note that the sequence number of the root node is 0 still 1, This is for the children pos It's influential .

Such as LeetCode The first 662 topic , I want you to find the width of the binary tree , Mainly, there may be a large area without nodes in the middle , It is not easy to traverse with normal sequence .

Ideas ： Sequence traversal + Using the properties of the queue's head and tail

Before each cycle , Get the first and last elements in the current queue , According to their pos The difference between the , Maintenance ans, That is, the maximum width .

class MyNode{
    TreeNode node;
    int depth;
    int pos;

    public MyNode(TreeNode node, int depth, int pos) {
        this.node = node;
        this.depth = depth;
        this.pos = pos;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Deque<MyNode> queue = new LinkedList<>();
        int ans = 0;
        queue.add(new MyNode(root,0,0));
        while (!queue.isEmpty()){
            int size = queue.size();
            ans = Math.max(queue.getLast().pos-queue.getFirst().pos+1,ans);
            while (size > 0){
                MyNode myNode = queue.remove();
                if (myNode.node.left != null){
                    queue.add(new MyNode(myNode.node.left,myNode.depth+1,myNode.pos*2+1));
                }
                if (myNode.node.right != null){
                    queue.add(new MyNode(myNode.node.right,myNode.depth+1,myNode.pos*2+2));
                }
                size--;
            }
        }
        return ans;
    }
}