Introduction: The construction of ordinary binary tree

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){} // No arguments
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val , TreeNode left , TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code

The first part verifies the properties of binary tree

1. Find the depth of the binary tree

Leetcode-cn.com/problems/ma…

class Solution {
    // Recursion: the greater value + 1 in the left and right child heights of the binary tree
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1; }}Copy the code

2. Find the minimum depth of the binary tree

Leetcode-cn.com/problems/mi…

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int l = minDepth(root.left);
        int r = minDepth(root.right);
        if(l == 0) return r + 1;
        else if(r == 0) return l+1;
        return Math.min(l, r) + 1; }}Copy the code

3. Determine if the binary tree is balanced

Leetcode-cn.com/problems/ba…

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        // The following three conditions are met
        return isBalanced(root.left) && isBalanced(root.right) && Math.abs(left-right) <= 1;
    }

    int maxDepth(TreeNode root){
        if(root == null) return 0;
        return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1; }}Copy the code

4. Flip the binary tree

Leetcode-cn.com/problems/in…

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        // First invert the left and right subtrees of the current node
        TreeNode cur = root.left;
        root.left = root.right;
        root.right = cur;
        // Recursively flips the left and right child
        invertTree(root.left);
        invertTree(root.right);
        returnroot; }}Copy the code

5. Determine whether binary trees are symmetric

Leetcode-cn.com/problems/sy…

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isMirror(root.left,  root.right);
    }

    boolean isMirror(TreeNode l , TreeNode r){
        if(l == null && r == null) return true;
        if(l == null || r == null) return false;
        if(l.val ! = r.val)return false;
        returnisMirror(l.left , r.right) && isMirror(l.right , r.left); }}Copy the code

6. Determine whether binary trees are the same

Leetcode-cn.com/problems/sa…

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val ! = q.val)return false;
        return isSameTree(p.left ,q.left) && isSameTree(p.right , q.right);
    }
Copy the code

7. Determine whether a binary tree is a subtree of another binary tree

Leetcode-cn.com/problems/su…

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) return false;
        if(t == null) return true;
        //// check whether it is a subtree of the left/right subtree or the same as the current tree
        return isSame(s , t) || isSubtree(s.left , t) || isSubtree(s.right , t);
    }

    boolean isSame(TreeNode s , TreeNode t){
        if(s == null && t == null) return true;
        if(s == null || t == null) return false;
        if(s.val ! = t.val)return false;
        returnisSame(s.left , t.left) && isSame(s.right , t.right); }}Copy the code

8. Diameter of binary tree

Leetcode-cn.com/problems/di…

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        dfs(root); // Walk through each node and calculate the longest path with each node as the center point (left side length + right side length)
        return res;
    }

    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;
        res = Math.max(res , leftSize + rightSize); // Update res
        returnMath.max(leftSize , rightSize); }}// Solution 2: Get the maximum height of the left and right subtrees centered on each node.
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return res;
    }

    void dfs(TreeNode root){
        if(root == null)  return;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        res = Math.max(res , l + r);
        dfs(root.left);
        dfs(root.right);
    }

    int maxDepth(TreeNode root){
        if(root == null) return 0;
        return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1; }}Copy the code

9. Maximum path sum of binary tree

Leetcode-cn.com/problems/bi…

class Solution {
    // As in the previous problem, the only difference is that the maximum path sum of left and right subnumbers is discarded as a negative number
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return res;
    }

    int dfs(TreeNode root){
        if(root == null) return 0;
        int leftSum = Math.max(0 , dfs(root.left));
        int rightSum = Math.max(0 , dfs(root.right));
        res = Math.max(res , leftSum + rightSum + root.val);
        returnMath.max(leftSum , rightSum) + root.val; }}Copy the code

10. The longest identically valued path of a binary tree

Leetcode-cn.com/problems/lo…

// The same idea as the previous two questions
class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root == null) return 0;
        dfs(root);
        return res;
    }

    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;
        
        // The only difference is that when the current node is different from the left node, the corresponding size = 0;
        if(root.left == null|| root.val ! = root.left.val) leftSize =0;
        if(root.right == null|| root.val ! = root.right.val) rightSize =0;
        res = Math.max(res , leftSize + rightSize);
        returnMath.max(leftSize,rightSize); }}Copy the code

11. The most recent common ancestor of binary trees

Leetcode-cn.com/problems/lo…

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return root;
        if(root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left , p , q);
        TreeNode r = lowestCommonAncestor(root.right , p , q);
        if(l == null) return r;
        if(r == null) return l;
        returnroot; }}Copy the code

The second part is the ergodic problem of binary tree

1. Sequential traversal of binary tree — left and middle

Leetcode-cn.com/problems/bi…

// We can write it recursively
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root , res);
        return res;
    }

    void dfs(TreeNode root , List<Integer> res){
        if(root == null) return; res.add(root.val); dfs(root.left , res); dfs(root.right, res); }}// Non-recursive
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        // press root into the stack
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(! stack.isEmpty()){ TreeNode curNode = stack.pop(); res.add(curNode.val);// Each pop-up node is added to the RES
            // Make sure to press the right child first and then the left child
            if(curNode.right ! =null) stack.push(curNode.right);
            if(curNode.left ! =null) stack.push(curNode.left);
        }
        returnres; }}Copy the code

2. Middle order traversal of binary tree — left, middle and right

Leetcode-cn.com/problems/bi…

// We can write it recursively
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root , res);
        return res;
    }

    void dfs(TreeNode root , List<Integer> res){
        if(root == null) return; dfs(root.left , res); res.add(root.val); dfs(root.right, res); }}// Non-recursive
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        / / the fact
        while(! stack.isEmpty() || cur ! =null) {//1. Press left first
            while(cur ! =null){
                stack.push(cur);
                cur = cur.left;
            }
            //2. The node is added
            TreeNode curNode = stack.pop();
            res.add(curNode.val);
            //3. Finally add the right child node
            cur = curNode.right;
        }
        returnres; }}Copy the code

3. Backorder traversal of binary tree — left and right center

Leetcode-cn.com/problems/bi…

// We can write it recursively
class Solution {
     List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) return res;
        dfs(root , res);
        return res;
    }

    void dfs(TreeNode root , List<Integer> res){
        if(root == null) return; dfs(root.left , res); dfs(root.right, res); res.add(root.val); }}// Non-recursive - order traversal backwards
class Solution {
    / / monitored
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(! stack.isEmpty()){ TreeNode curNode = stack.pop(); res.addFirst(curNode.val);if(curNode.left ! =null) stack.push(curNode.left);
            if(curNode.right ! =null) stack.push(curNode.right);
        }
        returnres; }}Copy the code

4. Sequence traversal of binary tree

Leetcode-cn.com/problems/bi…

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>(); // Queue the number of nodes in each layer
        queue.add(root);
        while(! queue.isEmpty()){int count = queue.size(); // The number of nodes in this layer
            List<Integer> list = new ArrayList<>();
            while(count > 0){
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                count--;
                if(curNode.left ! =null) queue.add(curNode.left); // Add nodes at the next level
                if(curNode.right ! =null) queue.add(curNode.right);
            }
            res.add(list);
        }
        returnres; }}Copy the code

5. Zigzag traversal of binary trees

Leetcode-cn.com/problems/bi…

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>(); // Queue the number of nodes in each layer
        queue.add(root);
        while(! queue.isEmpty()){int count = queue.size(); // The number of nodes in this layer
            List<Integer> list = new ArrayList<>();
            while(count > 0){
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                count--;
                if(curNode.left ! =null) queue.add(curNode.left); // Add nodes at the next level
                if(curNode.right ! =null) queue.add(curNode.right);
            }
            if(res.size() % 2= =1) Collections.reverse(list);
            res.add(list);
        }
        returnres; }}Copy the code

6. Right view of the binary tree

Leetcode-cn.com/problems/bi…

class Solution {
    // Only the last value is saved at a time
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()){int count = queue.size();
            int tem = 0;
            while(count > 0){
                TreeNode curNode = queue.poll();
                tem = curNode.val;
                count--;
                if(curNode.left ! =null) queue.add(curNode.left);
                if(curNode.right ! =null) queue.add(curNode.right);
            }
            res.add(tem);
        }
        returnres; }}Copy the code

7. Determine if it is a complete binary tree

Leetcode-cn.com/problems/ch…

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // Set a flag to true if null is encountered for each layer. If null is encountered for this layer, it indicates that the binary tree is not complete
        boolean flag = false;
        while(! queue.isEmpty()){ TreeNode curNode = queue.poll();if(curNode  == null){
                flag = true;
                continue;
            }
            if(flag) return false;
            queue.add(curNode.left);
            queue.add(curNode.right);
        }
        return true; }}Copy the code

8. The maximum width of a binary tree

Leetcode-cn.com/problems/ma…

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        int res = 1;
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> indexQueue = new LinkedList<>();// Record the index position of the node
        queue.add(root);
        indexQueue.add(1);
        while(! queue.isEmpty()){int count = queue.size();
            int l = indexQueue.peek();
            while(count > 0){
                TreeNode curNode = queue.poll();
                int r = indexQueue.poll(); // Index value of curNode
                count--;
                res = Math.max(res , r - l + 1); / / update the res
                if(curNode.left ! =null){
                    queue.add(curNode.left);
                    indexQueue.add(r * 2);
                }
                if(curNode.right ! =null){
                    queue.add(curNode.right);
                    indexQueue.add(r * 2 + 1); }}}returnres; }}Copy the code

9. The maximum value of each row of the binary tree

Leetcode-cn.com/problems/fi…

public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()){int count = queue.size();
            int tem = Integer.MIN_VALUE;
            while(count > 0){
                TreeNode curNode = queue.poll();
                tem = Math.max(tem , curNode.val);
                if(curNode.left ! =null) queue.add(curNode.left);
                if(curNode.right ! =null) queue.add(curNode.right);
                count--;
            }
            res.add(tem);
        }        
        return res;
    }

Copy the code

10. Binary tree serialization and deserialization

Leetcode-cn.com/problems/se…

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(! queue.isEmpty()){ TreeNode curNode = queue.poll();if(curNode ! =null){
                sb.append(curNode.val).append(",");
                queue.add(curNode.left);
                queue.add(curNode.right);
            }else sb.append("null,");
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] nums = data.substring(1 , data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nums[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int index = 1;
        while(! queue.isEmpty()){ TreeNode curNode = queue.poll();if(! nums[index].equals("null")){
                curNode.left = new TreeNode(Integer.parseInt(nums[index]));
                queue.add(curNode.left);
            }
            index++;
            if(! nums[index].equals("null")){
                curNode.right = new TreeNode(Integer.parseInt(nums[index]));
                queue.add(curNode.right);
            }
            index++;
        }
        returnroot; }}Copy the code