Binary tree practice binary tree traversal recursion 257, 100, 222, 101, 226, 437, 563, 617, 572, 543, |687

257. All paths of binary tree

Given a binary tree , Return all paths from the root node to the leaf node .

explain : A leaf node is a node that has no children .

Example :

Input :

1
/
2 3

5

Output : [“1->2->5”, “1->3”]

explain : The path from all root nodes to leaf nodes is : 1->2->5, 1->3
Answer key ：
1）dfs
2）bfs The queue determines whether it is a leaf node , Not at the end of the line , Is added to the path until the queue is empty
solution：

class Solution {
    
    public List<String> binaryTreePaths(TreeNode root) {
    
        List<String> res=new ArrayList<>();
        if(root==null) return res;
        dfs(root,"",res);
        return res;
    }
    public void dfs(TreeNode root,String cur,List<String> res){
    
        if(root==null) return;
        cur+=root.val;
        if(root.left==null&&root.right==null) res.add(cur);
        else {
    
         dfs(root.left,cur+"->",res);
         dfs(root.right,cur+"->",res);
    }
    }
}

543. The diameter of a binary tree

Given a binary tree , You need to calculate its diameter and length . The diameter length of a binary tree is the maximum of the path length of any two nodes . This path may or may not pass through the root node .
Answer key ： recursive Traverse every node , Calculate the longest path （ Side length of left subtree + The side length of the right subtree ）, Update global variables max.

class Solution {
    
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        dfs(root);
        return max;
    }
    
    private int dfs(TreeNode root) {
    
        if (root.left == null && root.right == null) {
    
            return 0;
        }
        int leftSize = root.left == null? 0: dfs(root.left) + 1;
        int rightSize = root.right == null? 0: dfs(root.right) + 1;
        max = Math.max(max, leftSize + rightSize);
        return Math.max(leftSize, rightSize);
    }  
}

563. The slope of the binary tree

Given a binary tree , Calculate the slope of the whole tree .
The slope of a tree node is defined as , The absolute value of the difference between the sum of the nodes of the left subtree and the sum of the nodes of the right subtree . The slope of the empty node is 0.
The slope of the whole tree is the sum of the slopes of all its nodes ,
Answer key ：
1） recursive
The slope of the whole tree is the sum of the slopes of all its nodes , Recursively calculate the slope of each node . That is to find the slope sum of the left subtree of each node And Right subtree slope and ;
The slope and of the subtree = The value of the root node of the subtree + The slope and of the left subtree of the subtree + The sum of the slopes of the right subtree of the subtree ; Continue to break down , Until it decomposes into an empty tree , The slope of the empty tree is 0, For recursive exit .
sloution：
1）java Math.abs() Method to find the absolute value

class Solution {
    
    public int findTilt(TreeNode root) {
    
    if(root==null) return 0;
    return Math.abs(s(root.left)-s(root.right)) +findTilt(root.left)+findTilt(root.right);
    }
    private int s(TreeNode root){
    
    if(root == null) return 0;    
    return root.val + s(root.right) +s(root.left);
    }
}

617. Merge binary tree

Given two binary trees , Imagine when you overlay one of them on the other , Some nodes of two binary trees will overlap .
You need to merge them into a new 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 .

Answer key ：
recursive ： The application of preorder traversal
sloution：

class Solution {
    
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    
        if (t1 == null && t2 == null) {
    
            return null;}
    TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
    root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
    root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
    return root;
}
}

226. /27. Flip binary tree

Answer key ：
1） recursive
2） iteration ： queue . As long as the queue is not empty , Just keep getting out of the queue , Then swap the left and right child nodes of this node , Then put the child nodes into the queue , Finally, return to the root node
sloution:
1） recursive c++

class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
        if (root == NULL) {
    
            return NULL;
        }
        swap(root->left, root->right);
        invertTree(root->left);
       invertTree(root->right);
        return root;
    }
};

2） iteration official java

public TreeNode invertTree(TreeNode root) {
    
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
    
        TreeNode current = queue.poll();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
    return root;
}

101. Symmetric binary tree

Given a binary tree , Check if it is mirror symmetric .
Answer key ：
1） recursive Complexity O(n)
2） iteration ： Introduction queue , A common way to rewrite recursion into iteration .
Every time pop Compare the value of two nodes , Then insert the left and right child nodes of the two nodes into the queue in the opposite order .
sloution：
1） recursive java

class Solution {
    
    public boolean isSymmetric(TreeNode root) {
    
        return cmp(root,root);
    }
    private boolean cmp(TreeNode t1,TreeNode t2){
    
        if(t1==null && t2==null) return true;
        if(t1==null || t2==null) return false;
        if(t1.val!=t2.val) return false;
        return cmp(t1.left,t2.right) && cmp(t1.right,t2.left);
    }
}

2） iteration c++ Official explanation ：

class Solution {
    
public:
    bool check(TreeNode *u, TreeNode *v) {
    
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
    
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
    
        return check(root, root);
    }
};

222. The number of nodes in a complete binary tree

Give a completely binary tree , Find out the number of nodes of the tree .
The definition of a complete binary tree is as follows ： In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer . If the bottom layer is No h layer , Then the layer contains 1~ 2h Nodes .
namely ： An empty tree or its leaf nodes are only on the last two floors , If the last layer is not satisfied, the leaf node is only on the far left .
Answer key ：
1）java recursive -> The properties of complete binary trees are not used

class Solution {
    
    public int countNodes(TreeNode root) {
    
        if(root==null) return 0;
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

2） Define the layer height of the left subtree left, The height of the right subtree right.
If equal , The left subtree is a full binary tree , The total number of nodes in the left subtree is 2^left -1, Plus the current one root node , It is 2^left , Then the recursive statistics of the right subtree .
Otherwise, the right subtree is full of binary trees , Right subtree node +root node , The total number is 2^right. Then recursively search the left subtree .
notes ： An operation Moving left is equivalent to *2

class Solution {
    
    public int countNodes(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if (left == right) {
    
            return countNodes(root.right) + (1 << left);
        } else {
    
            return countNodes(root.left) + (1 << right);
        }
    }
// Calculate the number of layers 
    private int countLevel(TreeNode root) {
    
        int level = 0;
        while (root != null) {
    
            level++;
            root = root.left;
        }
        return level;
    }
}

100. Same tree

Given two binary trees , Write a function to verify that they are the same . If two trees are the same in structure , And the nodes have the same value , They are the same .

Answer key ：
recursive Three kinds of judgment
1、 All is empty 、 identical
2、 An empty 、 One is not empty , Different
3、 Are not empty, but val Different

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        if(p==null&&q==null)  return true;
        if(p!=null && q!=null && p.val==q.val){
    
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
        else return false;
    }
}

572. The subtree of another tree

Given two non empty binary trees s and t, test s Whether and t Subtrees with the same structure and node values .s A subtree of includes s One node of and all descendants of this node .s It can also be seen as a subtree of its own .
Answer key ：
Double recursive
Or the two trees are equal
Or this tree is a subtree of the left tree
Or this tree is a subtree of the right tree

sloution：

class Solution {
    
    public boolean isSubtree(TreeNode s, TreeNode t) {
    
    if (t==null) return true;
    if (s==null) return false;
    return isSubtree(s.right,t) || isSubtree(s.left,t) || isSameTree(s,t);
    }

    public boolean isSameTree(TreeNode s, TreeNode t){
    
    if(s==null&t==null) return true;
    if(s!=null && t!=null && s.val==t.val){
     
    return isSameTree(s.left,t.left) && isSameTree(s.right,t.right);
        }
        else return false;
    }
}

404. The second of binary search tree k Big node

Given a tree Binary search tree , Find the second one k Big nodes .

Answer key ：
1） The sequence obtained by middle order traversal is ordered （ Increasing ）
2） By question no k Large is the reverse order of middle order traversal ： Right root left The first k Small ： Left root right

sloution：
1） Middle order traversal ArrayList Record

class Solution {
    
    public int kthLargest(TreeNode root, int k) {
    
        List<Integer> list = new ArrayList<>();
        helper(root, list);
        return list.get(list.size() - k);
    }
    
    private void helper(TreeNode root, List<Integer> list) {
    
        if (root == null) return;
        if (root.left != null) helper(root.left, list);
        list.add(root.val);
        if (root.right != null) helper(root.right, list);
    }
}

2） Recursive optimization ： Traverse to the k Big stop

class Solution {
    
    private int ans = 0, cnt = 0;
    public int kthLargest(TreeNode root, int k) {
    
        dfs(root, k);
        return ans;
    }
    private void dfs(TreeNode root, int k) {
    
        if(root == null) return ;
        dfs(root.right, k);
        if(++cnt == k) {
    
            ans = root.val;
        }
        dfs(root.left, k);
    }
}

3） iteration ： Utilization stack