This article continues to talk about the recursive routine of binary trees.
1, Determine whether the binary tree is a search binary tree
Search binary tree definition: for any subtree with X as the head in a binary tree, the left subtree is smaller than X and the right subtree is larger than x. (the classic search binary tree has no duplicate values)
1. Classic practice
Medium order traversal, the result is incremental, indicating that this is a search binary tree.
2. Recursive routine idea
Analyze any subtree with X as the head, and meet the condition that the subtree with X as the head is the search binary tree (list all possibilities)
1) The left subtree is a search binary tree
2) The right subtree is a search binary tree
3) The maximum value of the left subtree is less than X
4) The minimum value of the right subtree is greater than X
Only by satisfying these four conditions can we say that the subtree with X as the head is a balanced binary tree.
Here's the problem: at this time, I found that the results I need to obtain from the left subtree and the right subtree are inconsistent (one is to the minimum value and the other is to the maximum value), which is difficult to piece together recursion. how? It's easy to say that we directly seek the complete set (children only make choices, and adults do not make choices). We seek the maximum and minimum values for the left subtree, and so do the right subtree.
That is, every time we search the binary tree, maximum value and minimum value from the left subtree and right subtree, although we only return whether to search the binary tree, we need the maximum value and minimum value to help us judge whether to search, so we can define the following Info class
/**
* @author Java And algorithm learning: Monday
*/
public static class Info {
public boolean isSearch;
public int max;
public int min;
public Info(boolean isSearch, int max, int min) {
this.isSearch = isSearch;
this.max = max;
this.min = min;
}
}
3. Recursive routine code
(1) First, judge whether it is good to set when the node is empty. At this time, it is not good to set. When the node is empty, max and min are not easy to specify. Therefore, when the node is empty, it will directly return null, and then deal with this null during recursion.
(2) Then write the code of the recursive routine according to all the possibilities listed. Because the whole recursion is to be formed, the Info class must be returned at each step. (no brain gets the Info of the left and right subtrees, pieces together his own Info, and returns his own Info)
/**
* Determine whether it is a recursive routine for searching binary tree
*
* @author Java And algorithm learning: Monday
*/
public static Info process(Node x) {
// When null, max and min cannot be assigned, so null is returned here
if (x == null) {
return null;
}
// Get the data of left and right subtrees
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// Piece together your own data
boolean isSearch = true;
// The current node is not a search binary tree
// 1. The left subtree is not a search binary tree
// 2. The right subtree is not a search binary tree
// 3. The maximum value of the left subtree is greater than the current node
// 4. The minimum value of the right subtree is less than the current node
if (leftInfo != null && (!leftInfo.isSearch || leftInfo.max >= x.value)) {
isSearch = false;
}
if (rightInfo != null && (!rightInfo.isSearch || rightInfo.min <= x.value)) {
isSearch = false;
}
int max = x.value;
int min = x.value;
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
}
return new Info(isSearch, max, min);
}
(3) The main function calls the recursive method to get the result
/**
* @author Java And algorithm learning: Monday
*/
public static boolean isSearchBinaryTree(Node head) {
if (head == null) {
return true;
}
return process(head).isSearch;
}
2, Maximum distance of binary tree
Given a binary tree, there is a distance between any two nodes, and the maximum distance of the whole binary tree is returned. The distance between two nodes represents the number of nodes on the shortest path from one node to another (including the two nodes themselves)
1. Recursive routine idea
Firstly, the binary tree with X as the head is analyzed. There are two kinds of possibilities of its maximum distance, not through X and through X.
Without X: the maximum distance between the left subtree and the right subtree needs to be obtained
After X: (left tree height + right tree height + 1) is the maximum distance
That is, each time we need the maximum distance and height data from the left subtree and the right subtree, and finally take the maximum distance of the left subtree and the maximum distance of the right subtree, (left tree height + right tree height + 1) as the maximum distance of the whole tree. Although we only return the maximum distance in the end, we need height to help us calculate the maximum distance, so we can define the following Info class
/**
* @author Java And algorithm learning: Monday
*/
public static class Info {
public int height;
public int maxDistance;
public Info(int height, int maxDistance) {
this.height = height;
this.maxDistance = maxDistance;
}
}
2. Recursive routine code
(1) First, judge whether it is good to set the empty node. At this time, it is good to set. When the node is empty, new Info(0, 0), that is, it is considered that the height of the empty node is 0 and the maximum distance is 0.
(2) Then write the code of the recursive routine according to all the possibilities listed. Because the whole recursion is to be formed, the Info class must be returned at each step. (no brain gets the Info of the left and right subtrees, pieces together his own Info, and returns his own Info)
/**
* Recursive routine writing method for finding the maximum distance of binary tree
*
* @author Java And algorithm learning: Monday
*/
public static Info process(Node x) {
if (x == null) {
return new Info(0, 0);
}
// Get the information of left and right subtrees
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// Piece together your own information
// The maximum height is the maximum height of the left and right subtrees + 1
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// The maximum distance is the maximum distance of the left subtree, the maximum distance of the right subtree, (left tree height + right tree height + 1)
int maxDistance = Math.max((leftInfo.height + rightInfo.height + 1),
Math.max(leftInfo.maxDistance, rightInfo.maxDistance));
return new Info(height, maxDistance);
}
(3) The main function calls the recursive method to get the result
/**
* @author Java And algorithm learning: Monday
*/
public static int maxDistance(Node head) {
if (head == null) {
return 0;
}
return process(head).maxDistance;
}
This is the second part of the binary tree recursive routine solution, combined with Last Did you find something new. This time, we learned how to deal with different values to be obtained from the left and right subtrees, and how to deal with when it is difficult to set values when the node is empty.