Today we’re going to continue the recursion of binary trees.
1. Determine if it is a full binary tree
Full binary tree definition: For a binary tree of height H, the number of nodes is (2^ H-1).
1, recursive routine thinking
According to the definition of full binary tree, we only need to obtain height and node number each time.
That is, we need the height and the number of nodes from the left and right subtrees every time, and then judge whether it is a full binary tree according to the relationship between the height and the number of nodes. So you can define the following Info class
/ * * *@authorJava and algorithm learning: Monday */
public static class Info {
public int height;
public int nodes;
public Info(int height, int nodes) {
this.height = height;
this.nodes = nodes; }}Copy the code2. Recursive routine code
(1) First determine whether it is good to set the node when it is empty. At this time, it is good to set. When the node is empty, new Info(0, 0) means that the height of the node is 0 and the number of nodes is 0.
(2) Then code the recursion pattern based on all the possibilities listed, returning the Info class at each step since the whole recursion is required. (Get Info of left and right subtrees, piece together Info of own, return Info of own)
/ * * *@authorJava and algorithm learning: Monday */
public static Info process(Node x) {
if (x == null) {
return new Info(0.0);
}
// Get information about the left and right subtrees
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// Piece together your own information
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
int nodes = leftInfo.nodes + rightInfo.nodes + 1;
return new Info(height, nodes);
}
Copy the code(3) The main function calls the recursive method to get the result
/ * * *@authorJava and algorithm learning: Monday */
public static boolean isFull(Node head) {
if (head == null) {
return true;
}
Info process = process(head);
return (1 << process.height) - 1 == process.nodes;
}
Copy the codeAll code address: https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/IsFullBinaryTree.java
Find the node number of the largest subsearch binary tree in the binary tree
Given a binary tree, the whole may or may not be a search binary tree, but some of its subtrees are search binary trees, and we want to find the number of nodes in the subsearch binary tree with the largest number of nodes.
1, recursive routine thinking
To find the largest subsearch binary tree, there are two possibilities, including the head node of the binary tree and not including the head node of the binary tree.
(1) No head node is included: the maximum number of nodes searched in the left tree and the maximum number of nodes searched in the right tree are required
(2) including the head node: it is necessary to determine whether the left tree is a binary tree, whether the right tree is a binary tree, whether the maximum value of the left tree is smaller than the head node, whether the minimum value of the right tree is larger than the head node, and also the number of nodes of the left tree and the right tree.
In other words, we need to search the maximum number of nodes in the binary tree, whether to search the binary tree, Max, min, and the number of nodes from the left and right trees each time. However, it can be simplified. If the maximum number of nodes in the binary tree is equal to the number of nodes, it means that the whole subtree is searching the binary tree. Therefore, it can be simplified as the number of nodes, Max, min, and number of nodes in the maximum search binary tree. Although we only return the number of nodes at last, we need whether to search binary tree, Max and min to assist in solving the number of nodes. Finally, you can define the following Info class
/ * * *@authorJava and algorithm learning: Monday */
public static class Info {
// The maximum subtree size that satisfies the search criteria of binary tree
public int maxSubSize;
public int max;
public int min;
// The number of nodes in the entire subtree
public int allSize;
public Info(int maxSubSize, int max, int min, int allSize) {
this.maxSubSize = maxSubSize;
this.max = max;
this.min = min;
this.allSize = allSize; }}Copy the code2. Recursive routine code
(1) First determine whether it is good to set the node when it is null. It is not good to set the node when it is null. Max and min can not be specified when the node is null.
(2) Then code the recursion pattern based on all the possibilities listed, returning the Info class at each step since the whole recursion is required. (Get Info of left and right subtrees, piece together Info of own, return Info of own)
/ * * *@authorJava and algorithm learning: Monday */
public static Info process(Node x) {
if (x == null) {
return null;
}
// Get the left and right subtrees
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// Piece together your own information
int max = x.value;
int min = x.value;
int allSize = 1;
if(leftInfo ! =null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
allSize += leftInfo.allSize;
}
if((rightInfo ! =null)) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
allSize += rightInfo.allSize;
}
// Maximum search binary tree size for left tree
int p1 = -1;
if(leftInfo ! =null) {
p1 = leftInfo.maxSubSize;
}
// Maximum search binary tree size for right tree
int p2 = -1;
if(rightInfo ! =null) {
p2 = rightInfo.maxSubSize;
}
// The largest subtree contains a head node
int p3 = -1;
// The left tree is a search binary tree
boolean leftSearch = leftInfo == null || leftInfo.maxSubSize == leftInfo.allSize;
// The right tree is a search binary tree
boolean rightSearch = rightInfo == null || rightInfo.maxSubSize == rightInfo.allSize;
if (leftSearch && rightSearch) {
// Whether the maximum value of the left tree is smaller than the value of the current node
boolean lessMaxLessX = leftInfo == null || leftInfo.max < x.value;
// Whether the minimum value of the right tree is greater than the value of the current node
boolean rightMinMoreX = rightInfo == null || rightInfo.min > x.value;
// The value of p3 can be changed only when both of them are met
if (lessMaxLessX && rightMinMoreX) {
int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
p3 = leftSize + rightSize + 1; }}// Last modified, the current subtree maximum search two fork tree size
int maxSubSize = Math.max(p1, Math.max(p2, p3));
return new Info(maxSubSize, max, min, allSize);
}
Copy the code(3) The main function calls the recursive method to get the result
/ * * *@authorJava and algorithm learning: Monday */
public static int maxSubSearchBinaryTreeSize(Node head) {
if (head == null) {
return 0;
}
return process(head).maxSubSize;
}
Copy the codeAll code address: https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxSubSearchBinaryTreeSize.java
3. Summary of binary tree recursion routines
If you feel a little bit familiar with the recursion pattern of binary trees, it’s time to summarize the recursion pattern of binary trees.
1. Suppose we start with the X node. Suppose we can ask for any information from the left and right trees of X
2. Under the assumptions of the previous step, discuss the tree starting with X and list the possibilities of getting the answer (most important)
3. After listing all the possibilities, determine what information is needed for left and right trees
4. Complete the left tree information and the right tree information, which is the information returned by any subtree Info
Recursive functions all return Info, as required for every subtree
6, write code, in the code to consider how to integrate the information of the left tree and the information of the right tree into the information of the whole tree
After reading the previous few binary tree recursion routines, then look at this summary, is not easy to come.