2022-003arts: recursive routine of binary tree

ARTS：Algorithm、Review、Tip、Share

• Algorithm Algorithm problem
• Review English articles
• Tip Think back to a small skill learned at work this week
• Share Think about a technical point of view 、 Social hot spots 、 A product or a puzzle

Algorithm

Binary tree related topics , A large part can be solved by using the following recursive routine ：

1. Assume that any X A tree that is a head node , You can get any information from its left and right subtrees ;
2. Under the assumptions of the previous step , Discuss with X A tree that is a head node , The possibility of getting the answer ;
3. After listing all the possibilities , Determine what kind of information you need from the left tree and the right tree ;
4. Find the complete set of left tree information and right tree information , Is the information that any subtree needs to return S;
5. Recursive functions return S, Every sub tree asks so ;
6. Write code , In the code, consider how to integrate the information of the left tree and the information of the right tree into the information of the whole tree .

Relevant video materials ： Recursive routine of binary tree -time-57:45

958. The completeness test of binary tree

Given a binary tree root , Determine if it's a Perfect binary tree .

In a Perfect binary tree in , Except for the last level , All levels are completely filled , And all nodes in the last level are as far left as possible . It can contain 1 To 2h
The last level between nodes h .

Example 1：

Input ：root = [1,2,3,4,5,6] Output ：true explain ： Every floor before the last floor is full （ namely , The node value is {1} and {2,3}
The two layers ）, And all nodes in the last layer （{4,5,6}） As far left as possible . Example 2：

Input ：root = [1,2,3,4,5,null,7] Output ：false explain ： The value is 7 The node of is not as far to the left as possible .

Tips ：

The number of nodes of the tree is in the range [1, 100] Inside . 1 <= Node.val <= 1000

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree

Solution description

solution 1

First, let's talk about a solution that doesn't use the binary tree recursive routine , Judge whether a binary tree is a complete binary tree , The following two conditions can be passed ：

1. If a node has a right subtree , Then it must have a left subtree ;
2. After encountering incomplete nodes , The nodes behind the hierarchy traversal must be leaf nodes .

As mentioned above , You can use hierarchical traversal , Check the left and right child nodes of each node at once , Whether to violate any of the above conditions , If there is a direct return false, Otherwise, traverse all nodes , Then the tree is a complete binary tree .

solution 2

According to the idea of binary tree recursive routine , Under the assumption of the first step , Discuss with X Whether the tree with the head is a full binary tree , The possibilities of the answer are listed below ：

1. Left 、 All right subtrees are full binary trees , with X A tree with a head is a full binary tree ;
2. The left subtree is a non full binary tree 、 The right subtree is a full binary tree , And the height of the left subtree is higher than that of the right subtree 1;
3. The left subtree is a full binary tree 、 The right subtree is a non full binary tree , And left 、 The right subtree is equal in height .

Sum up , We need to turn left 、 The complete set of information required by the right subtree is ： Is it a complete binary tree 、 Whether it is a full binary tree 、 What is the height

Called recursively , Get the corresponding information on all subtrees , Then process the same information , See the following code implementation for details

coded

public boolean isCompleteTree(TreeNode root) {
    
	if (root == null) {
    
	    return true;
	}
	// method 01
	//Queue<TreeNode> queue = new LinkedList<>();
	//queue.add(root);
	//
	//boolean isStartLeaf = false;
	//TreeNode node;
	//TreeNode l;
	//TreeNode r;
	//while (!queue.isEmpty()) {
    
	// node = queue.poll();
	// l = node.left;
	// r = node.right;
	// if (r != null && l == null) {
    
	// return false;
	// }
	// if (isStartLeaf && (l != null || r != null)) {
    
	// return false;
	// }
	// if (l != null) {
    
	// queue.add(l);
	// }
	// if (r != null) {
    
	// queue.add(r);
	// }
	// if (!isStartLeaf && (l == null || r == null)) {
    
	// isStartLeaf = true;
	// }
	//}
	//return true;
	
	// method 02
	return process(root).isCBT;
}
	
public static class Info {
    
	public boolean isFull;
	public boolean isCBT;
	public int height;
	
	public Info(boolean full, boolean cbt, int h) {
    
	    isFull = full;
	    isCBT = cbt;
	    height = h;
	}
}
	
public static Info process(TreeNode xNode) {
    
	if (xNode == null) {
    
	    return new Info(true, true, 0);
	}
	Info leftInfo = process(xNode.left);
	Info rightInfo = process(xNode.right);
	
	int height = Math.max(leftInfo.height, rightInfo.height) + 1;
	boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
	boolean isCBT = false;
	if (isFull) {
    
	    isCBT = true;
	} else if (leftInfo.isCBT && rightInfo.isCBT) {
    
	
	    if (!leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 1) {
    
	        isCBT = true;
	    } else if (
	            leftInfo.isFull && rightInfo.isFull && leftInfo.height - rightInfo.height == 1
	    ) {
    
	        isCBT = true;
	    } else if (
	            leftInfo.isFull && !rightInfo.isFull && leftInfo.height == rightInfo.height
	    ) {
    
	        isCBT = true;
	    }
	}
	
	return new Info(isFull, isCBT, height);
}

Review

NewCollectionTypesExplained Some common business scenarios , Use JDK The implementation of the collection framework is cumbersome ,Guava In response to this problem , Yes JDK The collection framework type of , This article wiki It is introduced in detail ：

• Multiset It is used to count elements that may appear multiple times , It can be downloaded from unordered ArrayList、Map<E, Integer> Two API Understand from the perspective

Tip

The first working week after the year , Most of my colleagues were on compensatory leave two days ago , While completing relevant work this week , It is also mainly to be familiar with the previous business 、 Code , Encountered no document 、 Or there are documents and the description is simple , There is code but no comments 、 The code logic is disordered .

Apart from a few complaints , I can only ask myself more 、 Get familiar with 、 Start documenting .

Share

When you encounter business scenarios you need to be familiar with at work 、 Complex code flow , Effective means can be achieved by communicating with relevant colleagues , The more direct way is to actually go through the process by yourself ,debug Go through the relevant code , Although it may be troublesome , But it can go deep into the details , clarify 、 Sort out the possible questions at each node .

Not afraid of trouble 、 Be diligent in your hands .