Programming VIP

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      	// 1. Return empty box
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }else{
          	// 2. Queue village coarse
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                List<Integer> tmp = new ArrayList<>();
                while(size-- > 0){
                    TreeNode top = queue.poll();
                    tmp.add(top.val);
                    if(top.left != null){
                        queue.offer(top.left);
                    }
                    if(top.right != null){
                        queue.offer(top.right);
                    }
                }
                list.add(tmp);
            }
            return list;
        }
    }
}
[[A], [B, C], [D, E, F, G], [H, I, J], [K]]

Demonstrate the code execution steps in the OJ exercise

Normal sequence output

/*
1.Create a queue first
2.Put the root node in the queue
3.Cycle through all queue elements
4.Add current element to internal list
4.Then put the left subtree of the current element into the queue and then into the right subtree
5.The large ret adds the list after each new element is added
*/
private static void levelOrder(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            BinaryTreeNode top = queue.poll();
            System.out.print(top.val + " ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
    }
}
A B C D E F G H I J K

3.2 establishment of binary tree

3.2.1 construction of binary tree in pre order and middle order

class Solution {
    private int findInorderIndex(int[] inorder, int inbegin, int inend, int key){
        for(int i=inbegin; i<=inend; ++i){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){
        if(inbegin > inend){
            return null;
        }else{
            TreeNode root = new TreeNode(preorder[preIndex++]);
            int rootIndex = findInorderIndex(inorder, inbegin, inend, root.val);
            root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);
            root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);
            return root;
        }
    }

    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null){
            return null;
        }else{
            return buildTreeChild(preorder, inorder, 0, inorder.length-1);
        }
    }
}

At that time, the principle of recursion was also used to establish the binary tree, but the code of the printed node was replaced by the operation of generating the node and assigning a value to the node
The first node of the preorder traversal must be the root node, so we divide the left and right subtrees of the root node in the preorder traversal, and then recursively find the root node and divide the left and right subtrees. The termination condition of recursion is that the left of the interval must be greater than the right of the interval
Code idea:

Judge whether one of the pre sequence or middle sequence is null [ special case handling ]
Using buildTreeChild function to return root node
First construct the root node, and then recursively construct the left subtree and right subtree
The last root returned after all recursion is the root node of the tree

Demonstration diagram

The first search is the root node of preorder[preIndex] (the preIndex value is 0)
During the second partition, the new inend is rootIndex-1, so the resulting if (in begin > inend) return; The program returns to execute root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);
Third division
comprehensive

3.2.2 constructing binary tree in middle order and later order

class Solution {
    private int postIndex = 0;

    private int findInorderIndex(int[] inorder, int inbegin, int inend, int key){
        for(int i=inbegin; i<=inend; ++i){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int inbegin, int inend){
        if(inbegin > inend){
            return null;
        }else{
            TreeNode root = new TreeNode(postorder[postIndex--]);
            int rootIndex = findInorderIndex(inorder, inbegin, inend, root.val);
            root.right = buildTreeChild(inorder, postorder, rootIndex+1, inend);
            root.left = buildTreeChild(inorder, postorder, inbegin, rootIndex-1);
            return root;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null){
            return null;
        }else{
            postIndex = postorder.length-1;
            return buildTreeChild(inorder, postorder, 0, postIndex);
        }
    }
}

Post order traversal has the same idea as pre order change, but attention should be paid to the order [the last post order traversal is the root, and the first pre order traversal is the root]

Demonstration diagram
From the back to the front, the root node is the right node, so first build the right subtree and then the left subtree. The idea of traversal recursion is the same as the above, which will not be described here

The properties of a binary tree are summarized

Known preorder traversal and inorder traversal, we can determine the only binary tree
Given the middle order traversal and post order traversal, the unique binary tree can be determined

Thinking: given the preorder traversal and postorder traversal, can we build a unique binary tree

No, the reason is very simple. For example, the preorder traversal of a binary tree is ABC, and the postorder traversal is CBA. We can determine that the root node is a, but we can't determine the left and right subtrees of A. this tree has the following four possibilities

3.2.3 create string from binary tree

Solution 1

The left subtree is processed first, and then the right subtree is processed
Add brackets one by one according to the requirements of the topic

class Solution {
    private void tree2strChild(TreeNode root, StringBuffer stringBuffer){
        if(root == null){
            return;
        }else{
            stringBuffer.append(root.val);
            // 1. Processing left subtree
            if(root.left == null){
                if(root.right == null){
                    return;
                }else{
                    stringBuffer.append("()");
                }
            }else{
                stringBuffer.append("(");
                tree2strChild(root.left, stringBuffer);
                stringBuffer.append(")");
            }
            // 2. Processing right subtree
            if(root.right == null){
                return;
            }else{
                stringBuffer.append("(");
                tree2strChild(root.right, stringBuffer);
                stringBuffer.append(")");
            }
        }
    }

    public String tree2str(TreeNode root) {
        if(root == null){
            return "";
        }else{
            StringBuffer stringBuffer = new StringBuffer();
            tree2strChild(root, stringBuffer);
            return  stringBuffer.toString();
        }
    }
}

Solution 2
Less code, easy to understand, but low efficiency

Add parentheses in the form of recursive preorder traversal
After adding, delete the first and last parentheses

class Solution {
    private StringBuffer stringBuffer = null;
    private void tree2strChild(TreeNode root){
        if(root == null){
            return;
        }else{
            stringBuffer.append("("+root.val);
            tree2strChild(root.left);
            if(root.left == null && root.right != null){
                stringBuffer.append("()");
            }
            tree2strChild(root.right);
            stringBuffer.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root == null){
            return "";
        }else{
            stringBuffer = new StringBuffer();
            tree2strChild(root);
            stringBuffer.deleteCharAt(0);
            stringBuffer.deleteCharAt(stringBuffer.length()-1);
            return stringBuffer.toString();
        }
    }
}

3.2.4 pre order traversal of strings to build a binary tree

import java.util.Scanner;
import java.util.Stack;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char val){
        this.val = val;
    }
}

public class Main{

	// 1. The middle order traversal is carried out in an iterative manner
    private static void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }else{
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while(cur != null || !stack.empty()){
            	// 2. Left subtree collective stack
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }
    
    private static int index = 0;// Record the printed string subscript. Because it is recursive, you should use global variables instead of local variables
    private static  TreeNode createTree(String str){
        if(str == null){
            return null;
        }else{
            TreeNode root = null;
            // 1. Cross the empty node
            if(str.charAt(index) == '#'){
                ++index;
            }else{
                // 2. Recursively construct a binary tree in the form of left and right preorder roots
                root = new TreeNode(str.charAt(index++));
                root.left = createTree(str);
                root.right = createTree(str);
            }
            return root;
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String str = scanner.next();
            TreeNode root = createTree(str);
            inOrderTraversal(root);
            System.out.println();
        }
    }
}

3.2.5 merge binary tree

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    	// 1. If a node is null, another node will be returned
        if(root1 == null){
            return root2;
        }else if(root2 == null){
            return root1;
        }else{
        	// 2. If both nodes are not null, start merging the binary tree
            TreeNode root = new TreeNode(root1.val+root2.val);
            root.left = mergeTrees(root1.left, root2.left);
            root.right = mergeTrees(root1.right, root2.right);
            return root;
        }
    }
}

3.2.6 incremental binary tree

class Solution {
    private TreeNode cur = null;

    private void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }else{
            //1. Left
            inOrderTraversal(root.left);
            // 2. Root
            cur.right = root;
            root.left =
            // 3. Right
            inOrderTraversal(root.right);
        }
    }

    public TreeNode increasingBST(TreeNode root) {
        if(root == null){
            return null;
        }else{
            // 1. The puppet node is used to save the location of the cur node for return
            TreeNode newRoot = new TreeNode(-1);
            // 2. Mobile node
            cur = newRoot;
            inOrderTraversal(root);
            return newRoot.right;
        }
    }
}

3.3 analysis of classic topics

3.3.1 number of nodes

/*
Find the number of nodes
 Traversal idea: recursion increases by 1 every time it traverses [Online OJ may overturn: first call gerSize1 method with a small tree, and then call getSize1 with a large tree]
Subquestion idea: return 1+func()... With its own return value
 */
private static int size = 0;

private static void getSize1(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        ++size;
        getSize1(root.left);
        getSize1(root.right);
    }
}


private static int getSize2(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + getSize2(root.left) + getSize2(root.right);
    }
}

3.3.2 number of leaf nodes

/*
Find the number of leaf nodes
 Traversal idea: recursive traversal
 Subquestion idea: return 1+func()
 */
private static int leaftSize = 0;

private static void getLeafSize1(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        if (root.left == null && root.right == null) {
            ++leaftSize;
        } else {
            getLeafSize1(root.left);
            getLeafSize1(root.right);
        }
    }
}

private static int getLeafSize2(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    } else {
        if (root.left == null && root.right == null) {
            return 1;
        } else {
            return getLeafSize2(root.left) + getLeafSize2(root.right);
        }
    }
}

3.3.3 number of nodes in layer k

private static int getKLevelSize(BinaryTreeNode root, int k) {
    if (root == null || k < 1) {
        return 0;
    } else {
        if (k == 1) {
            return 1;
        } else {
            return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
        }
    }
}

3.3.4 find the node where val is located

private static BinaryTreeNode find(BinaryTreeNode root, String val) {
    if (root == null) {
        return null;
    } else {
        if (root.val.equals(val)) {
            return root;
        } else {
            BinaryTreeNode ret = find(root.left, val);
            if (ret != null && ret.val.equals(val)) {
                return ret;
            }
            ret = find(root.right, val);
            if (ret != null && ret.val.equals(val)) {
                return ret;
            }
            return null;
        }
    }
}

3.3.5 same tree

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1. Both are null: it means that the previous node and node values are equal, so they are equal; Or two empty nodes are equal
        if(p == null && q == null){
            return true;
        // 2. One node is traversed, but the other node is not null, so it is false    
        }else if(p == null || q == null){
            return false;
        }else{
            // 3. false if the node values are not equal
            if(p.val != q.val){
                return false;
            }else{
                // 4. Perform the next comparison recursively
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
    
}

3.3.6 another sub tree

class Solution {
      public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1. Both are null: it means that the previous node and node values are equal, so they are equal; Or two empty nodes are equal
        if(p == null && q == null){
            return true;
        // 2. One node is traversed, but the other node is not null, so it is false    
        }else if(p == null || q == null){
            return false;
        }else{
            // 3. false if the node values are not equal
            if(p.val != q.val){
                return false;
            }else{
                // 4. Perform the next comparison recursively
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 1. Two nullnull s are subtrees; Traverse the subtree of the leaf node [although it does not exist], indicating that the previous traversals are equal
        if(root == null && subRoot == null){
            return true;
        }else if(root == null && subRoot != null || root != null && subRoot == null){
            return false;
        }else{
            // 1. If two nodes are not empty and equal, they are subtrees
            if(isSameTree(root, subRoot)){
                return true;
            // 2. Recursively judge whether it is a subtree
            }else if(isSubtree(root.left, subRoot)){
                return true;
            }else if(isSubtree(root.right, subRoot)){
                return true;
            }else{
                return false;
            }
        }
    }
}

3.3.7 maximum depth of binary tree

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }else{
        	// 1. Calculate the height of the left subtree
            int left = maxDepth(root.left)+1;
            // 2. Calculate the height of the right subtree
            int right = maxDepth(root.right)+1;
            if(left>right){
                return left;
            }else{
                return right;
            }
        }
    }
}

3.3.8 balanced binary tree

class Solution {
    private int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int left = 1+maxDepth(root.left);
            int right = 1+maxDepth(root.right);
            return left>right?left:right;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }else{
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            if(Math.abs(left-right)>1){
                return false;
            }else{
                return isBalanced(root.left) && isBalanced(root.right);
            }
        }
    }
}

// 1. Optimized code: calculate the height difference between the left and right subtrees while calculating the height, without recursion twice
class Solution {
    private int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            if(left >= 0 && right >= 0 && Math.abs(left-right)<=1){
                return Math.max(left, right)+1;
            }else{
                return -1;
            }
        }
    }
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) > -1;
    }
}

3.3.9 symmetric binary tree

class Solution {
    private boolean isSameTree(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree == null) {
            return true;
        } else if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        } else {
            if (leftTree.val != rightTree.val) {
                return false;
            } else {
                /*
                1. The previous judgment steps are similar to comparing whether the binary tree is the same
                2. After that, the left of the left tree and the right of the right tree should be compared; Is the right of the left tree the same as the left of the right tree
                */
                return isSameTree(leftTree.left, rightTree.right) && isSameTree(leftTree.right, rightTree.left);
            }
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return isSameTree(root.left, root.right);
        }
    }
}

3.3.10 completeness test of binary tree

Use the queue feature to judge whether all the nodes are in the queue (including null nodes) and then out of the queue

/*
1. When a null node is encountered, it indicates that all complete binary trees have been traversed and exits
2. Pop up the element slowly at the end of the queue. If it is not null, it indicates that it is not a complete binary tree
*/
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }else{
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            // 1. Stop entering the queue until a null node is encountered
            while(!queue.isEmpty()){
                TreeNode top = queue.poll();
                if(top != null){
                    queue.offer(top.left);// When the program reaches the leaf node, it will also bring the null node into the queue. If a non null node is encountered during the subsequent peekpeek detection, it means that there are other leaf nodes after the null node is encountered. At this time, it must not be a complete binary tree
                    queue.offer(top.right);
                }else{
                    break;
                }
            }//When the program is executed here, it indicates that all nodes have been stored in the queue
            // 2. The node goes out of the queue and peek detects whether the element is null
            while(!queue.isEmpty()){
                TreeNode top = queue.peek();
                if(top != null){
                    return false;
                }else{
                    queue.poll();//Out of queue
                }
            }
            return true;
        }
    }
}

Optimization: simple and efficient judgment by comparing the number of nodes and subscripts

class Solution {
    private int n=0, p=0;

    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return true;// 1. Node traversal is completed
        }else if(k > 100){
            return false;// 2. Topic tip: there will be 1 to 100 nodes in the tree
        }else{
            ++n;// 3. Every time you traverse, the number of nodes will increase by one, and the subscript of the current node will be recorded
            p = Math.max(p, k);// 4. Because there are left and right subtrees, the maximum subscript should be selected each time
            return dfs(root.left, 2*k) && dfs(root.right, 2*k+1);
        }
    }

    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }else{
            if(!dfs(root, 1)){
                return false;// 1. false is returned when the number of nodes exceeds 100
            }else{
                return n == p;// 2. If it does not exceed 100 nodes, judge whether the number of nodes is equal to the maximum subscript number
            }
        }
    }
}

3.3.11 nearest father-in-law ancestor of binary tree

/*
left == null, right == null: return null
left != null, right != null: return root
left == null, right != null: return right
left != null, right == null: return left
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }else{
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null && right == null){
                return null;
            }else if(left != null && right == null){
                return left;
            }else if(left == null && right != null){
                return right;
            }else{
                return root;
            }
        }
    }
}

3.3.12 maximum width of binary tree