1. The binary tree
Node structure:
public class Node<V> {
V value;
Node<V> left;
Node<V> right;
}
Copy the code2. Binary tree traversal
2.1 the recursive sequence
There is a binary tree constructed as follows:
We traversed the above binary tree recursively:
public static void traversal(Node root) {
if (root == null) {
return ;
}
System.out.println(root.value);
traversal(root.left);
System.out.println(root.value);
traversal(root.right);
System.out.println(root.value);
}
Copy the codeThe results as follows: [1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1)
The result is the recursive order of the binary tree.
According to the recursive order, the value of each node is output for three consecutive or disconsecutive times. This means that in the case of recursively traversing a binary tree, the traversal method fragment invoked by each node will be accessed three times consecutively or disconsecutively. Why is that?
This will talk about the implementation mechanism of binary tree recursive traversal method.
2.2 Recursive execution mechanism
Abstract 2.1 code:
public static void traversal(Node root) {
// First access interval
if (root == null) {
return ;
}
// First access interval
traversal(root.left);
// Second access interval
// Second access interval
traversal(root.right);
// Third access interval
// Third access interval
}
Copy the codeThe above code is the skeleton of a binary tree for recursive operations. Using this skeleton, we can implement any binary tree operation. We analyze the execution flow of the skeleton from the Java function call mechanism.
The function is executed line by line from top to bottom:
-
Access this method for the first time: the first line of the method is executed — > traversal(root.left) to initiate the recursive invocation
-
Traversal (root.left) ends the recursion — > traversal(root.right) starts the recursion
-
Traversal (root.right) completes the recursive call — > the last line of the method is executed
Every time you access this method, even if nothing is done, you still access a snippet of the method.
This explains why 2.1 recursively traverses the binary tree, printing the value of each node three times. Because in the 2.1 code, the statement to output the value of the node is placed in the first access interval, the second access interval and the third access interval respectively. Therefore, three output statements are executed separately with three visits to the method.
Take a leaf node of a binary tree as an example to show the code snippet of accessing this method three times:
2.3 Recursive traversal
On the basis of recursive order, three kinds of recursive traversal can be processed. Preorder, middle order and post order traversal.
These three recursive traversal methods work for any binary tree. In essence, the recursive execution mechanism is used to select different times to print nodes in the process of accessing the method for three times, so as to realize three kinds of sequential recursive traversal.
2.3.1 Preorder traversal
Definition: For all subtrees, the root node is printed first, then all nodes in the left subtree, and finally all nodes in the right subtree.
Implementation logic: Print the node on the first access to this method, not the second and third.
The recursion order of 2.1 binary tree is [1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 7, 3, 1]
According to the above implementation logic, processing recursion sequence [1 (fx), 2) (), 4 (fx), 4, 4, 2, 5 (fx), 5, 5, 2, 1, 3), (), 6 (fx), 6, 6, 3, 7 (fx), 7, 7, 3, 1)
Results of successive traversal can be obtained [1, 2, 4, 5, 3, 6, 7]
Code:
public static void preOrderTraversal(Node root) {
if (root == null) {
return ;
}
System.out.println(root.value);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
Copy the code2.3.2 Order traversal
Definition: For all subtrees, print all nodes in the left subtree first, then the root node, and finally all nodes in the right subtree.
Implementation logic: Print the node on the second access to this method, not the first and third.
The recursion order of 2.1 binary tree is [1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 7, 3, 1]
, according to the above implementation logic processing recursion sequence [1, 2, 4, 4), (), 4, 2) (), 5, 5) (), 5, 2, 1), (), 3, 6, 6) (), 6, 3), (), 7, 7 (fx), 7, 3, 1)
Results of continuous traversal can be obtained [4, 2, 5, 1, 6, 3, 7]
Code:
public static void inOrderTraversal(Node root) {
if (root == null) {
return ;
}
inOrderTraversal(root.left);
System.out.println(root.value);
inOrderTraversal(root.right);
}
Copy the code2.3.3 Post-order traversal
Definition: For all subtrees, print all nodes in the right subtree first, then all nodes in the left subtree, and finally print the root node.
Implementation logic: Print the node on the third access to this method, not the first and second.
The recursion order of 2.1 binary tree is [1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 7, 3, 1]
According to the above implementation logic, processing recursion sequence [1, 2, 4, 4, 4), (), 2, 5, 5, 5) (), 2) (), 1, 3, 6, 6, 6) (), 3, 7, 7, 7 (fx), 3 (tick), 1 (fx)]
Results of subsequent traversal can be obtained [4, 5, 2, 6, 7, 3, 1]
Code:
public static void postOrderTraversal(Node root) {
if (root == null) {
return ;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.println(root.value);
}
Copy the code2.4 Non-recursive traversal
Any recursion can be changed to non-recursion. Since recursion is not metaphysics, and the system pushes you, you can certainly try to push yourself.
2.4.1 Preorder traversal
Implementation logic:
- Prepare a stack.
- The root node presses first.
- Iterative fixed process:
- Top node cur bomb stack.
- Print a cur.
- Cur’s right child presses first, left child presses again. (If one exists)
Code:
public static void preOrderTraversal(Node root) {
if (root == null) {
return ;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while(! stack.empty()) { Node cur = stack.pop(); System.out.println(cur.value);if(cur.right ! =null) {
stack.push(cur.right);
}
if(cur.left ! =null) { stack.push(cur.left); }}}Copy the code2.4.2 Sequential Traversal
Implementation logic:
- Prepare a stack.
- Iterative fixed process:
- Push all the left boundary nodes of the root node. (If one exists)
- Stack top node pops stack, and prints.
- Make the right child of the top element of the stack the new root node. (If one exists)
Note: left boundary node = root node + all left children of root node
Explanation: Why do we need to do this to achieve a non-recursive middle-order traversal? Because all trees can be decomposed by the left edge. Of course, it can also be decomposed by the right edge, just from a different Angle.
We push the left boundary onto the stack in the order of root first and then left, so the order of spring stack is left then root. So any left boundary is printed in the order of first left then root, and then when we pop a node, it goes around the right subtree again.
In this process, the print is always left bound, so the order is always left first and then root. The key is to make the left boundary of the right child go back to the left and then root. This shows that, for any subtree, the process is as follows:
Code:
public static void inOrderTraversal(Node root) {
if (root == null) {
return ;
}
Stack<Node> stack = new Stack<>();
// The stack is empty until the right leaf node hits the stack
while(! stack.isEmpty() || root ! =null) {
if(root ! =null) {
stack.push(root);
root = root.left;
} else{ root = stack.pop(); System.out.println(root.value); root = root.right; }}}Copy the code2.4.3 Sequential traversal
Implementation logic:
- Prepare two stacks.
- The root node pushes A first.
- Iterative fixed process:
- The top node of the stack cur stack A.
- Cur pushes B.
- Cur The left child presses A and the right child presses A. (If one exists)
- Eject all elements of stack B in sequence while printing.
Code:
public static void postOrderTraversal(Node root) {
if (root == null) {
return ;
}
Stack<Node> stackA = new Stack<>();
Stack<Node> stackB = new Stack<>();
stackA.push(root);
while(! stackA.isEmpty()) { Node cur = stackA.pop(); stackB.push(cur);if(cur.left ! =null) {
stackA.push(cur.left);
}
if(cur.right ! =null) { stackA.push(cur.right); }}while (!stackB.isEmpty()) {
System.out.println(stackB.pop().value);
}
}
Copy the code2.5 Depth-first Traversal
Pre-order traversal is depth-first traversal.
public static void depthFirstSearch(Node root) {
preOrderTraversal(root);
}
Copy the code2.6 Width first traversal
Implementation logic:
- Prepare a queue.
- The root node is queued first.
- Iterative fixed process:
- The head node cur exits the queue and prints.
- Cur left children into line. (If one exists)
- Cur right child in line. (If one exists)
Note:
- In Java, LinkedList is often used to simulate a chained queue.
- The characteristics of a queue are FIFO (first in, first out), with elements in at the end of the queue and elements out at the head of the queue.
Code:
public static void breadthFirstSearch(Node root) {
if (root == null) {
return ;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(! queue.isEmpty()) { Node cur = queue.poll(); System.out.println(cur.value);if(cur.left ! =null) {
queue.add(cur.left);
}
if(cur.right ! =null) { queue.add(cur.right); }}}Copy the code3. Binary tree printing
In the process of writing binary tree adjustments, if you want to see what the current binary tree looks like, it involves a problem: how to intuitively print a binary tree?
A welfare function is provided here. When viewing the result of the welfare function, turn the whole graph clockwise by 90°, which is the current binary tree.
Note when viewing the results:
- H1H: indicates the root node whose value is 1.
- ^2^ : indicates that the value of this node is 2 and the parent node is above and to the left.
- V3v: indicates that the value of this node is 3 and the parent node is lower to the left.
// Print interface
public static void printBinaryTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0."H".17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1."v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1."^", len);
}
public static String getSpace(int num) {
String space = "";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
Copy the code4. Serialization and deserialization
4.1 concept
Binary tree serialization means that a binary tree in memory is serialized into a string and stored in the hard disk.
Binary tree deserialization refers to deserializing the string in the hard disk into a binary tree and storing it in memory.
Each binary tree corresponds to a unique sequence of strings.
The nature of binary tree serialization and deserialization is traversal, so there are as many ways of traversal as there are ways of serialization. In this paper, preorder traversal is used to achieve serialization.
4.2 Serialization Rules
The whole binary tree character sequence consists of three parts:
- Value of each node
- _
- #
The value of each node is separated by “_”. If this object is null, value is replaced by “#”.
Here is:
4.3 code
4.3.1 serialization
public static String serialize(Node root) {
if (root == null) {
return "# _";
}
StringBuilder charSequence = new StringBuilder();
charSequence.append(root.value + "_");
charSequence.append(serialize(root.left));
charSequence.append(serialize(root.right));
return charSequence.toString();
}
Copy the code4.3.1 Deserialization
public static Node deserialize(String charSequence) {
// Unpack the character sequence into a queue
String[] values = charSequence.split("_");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < values.length; i ++) {
queue.add(values[i]);
}
// Restore the binary tree with a queue
return process(queue);
}
public static Node process(Queue<String> queue) {
String value = queue.poll();
// Check whether the current node is null
if ("#".equals(value)) {
return null;
}
Node root = new Node(Integer.parseInt(value));
root.left = process(queue);
root.right = process(queue);
return root;
}
Copy the code5. Special binary trees
5.1 Searching binary Trees
5.1.1 definition
-
An empty binary tree is a search binary tree.
-
For every root node in a nonempty binary tree, its left subtree has a smaller key, and its right subtree has a larger key.
-
In a classical search binary tree, there are no duplicate nodes.
5.1.2 graphic
5.1.3 Judgment search binary tree
The results of traversing a search binary tree must be in ascending order.
Note: middle order traversal can be implemented both recursively and nonrecursively, but in recursive implementation, the key of the previous node cannot be stored in the method fragment, so class members must be defined as global variable records. Therefore, it is not recommended to use recursive middle order traversal to judge the search binary tree.
Recursive solution:
// Global variables
private static Node pre = null;
public static boolean isBST(Node root) {
if (root == null) {
return true;
}
boolean isLeftBST = isBST(root.left);
if(! isLeftBST) {return false;
}
// Ascending judgment
if(pre ! =null && pre.value >= root.value) {
return false;
} else {
pre = root;
}
return isBST(root.right);
}
Copy the codeNon-recursive solution:
public static boolean isBST(Node root) {
if (root == null) {
return true;
}
Stack<Node> stack = new Stack<>();
// Record the previous node of the current node
Node pre = null;
while(! stack.isEmpty() || root ! =null) {
if(root ! =null) {
stack.push(root);
root = root.left;
} else {
Node cur = stack.pop();
// Ascending comparison
if(pre ! =null && pre.value >= cur.value) {
return false;
} else{ pre = cur; } root = cur.right; }}return true;
}
Copy the code5.2 Complete binary tree
5.2.1 definition
-
It’s full binary tree.
-
It’s not a full binary tree, but the dissatisfied level can only be the last level, and even the last dissatisfied level will be full from left to right.
5.2.2 graphic
5.2.3 Judging the complete binary tree
Ideas:
- Use width first traversal.
- If you’re walking through a node that has a right child and no left child, it’s not a complete binary tree.
- In the traversal process, if a node has left children and no right children or neither (left and right children are incomplete), then all nodes traversed afterwards must be leaf nodes.
Code:
public static boolean isCBT(Node root) {
if (root == null) {
return true;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// Switch that fires when left and right children are encountered and holds true
boolean flag = false;
while(! queue.isEmpty()) { Node cur = queue.poll();// Check whether the current node has a right child and no left child
if (cur.left == null&& cur.right ! =null) {
return false;
}
// Check whether the current node has no children or whether there are left children and no right children. The flag will be triggered when the node passes through for the first time
if (cur.left == null || cur.right == null) {
flag = true;
}
// Check whether all nodes traversed are leaf nodes when flag is set to true
if(flag && ! (cur.left ==null && cur.right == null)) {
return false;
}
if(cur.left ! =null) {
queue.add(cur.left);
}
if(cur.right ! =null) { queue.add(cur.right); }}return true;
}
Copy the code5.3 Full binary tree
5.3.1 definition
Let the maximum depth be L and the total number of nodes be N, which satisfies the binary tree of N = 2^ L-1.
5.3.2 graphic
5.3.3 Judging full binary tree
Ideas:
- The depth of the tree is obtained by sequential traversal.
- Width first traversal to find the total number of nodes in the tree.
- Check if it’s a full binary tree based on N = 2^L – 1.
Code:
public static boolean isFBT(Node root) {
if (root == null) {
return true;
}
int depth = getDepth(root);
int count = getCount(root);
// Check the formula
return count == (int) Math.pow(2, depth) - 1;
}
// Calculate the binary tree depth
public static int getDepth(Node root) {
if (root == null) {
return 0;
}
int leftD = getDepth(root.left);
int rightD = getDepth(root.right);
return Math.max(leftD, rightD) + 1;
}
// Calculate the total number of nodes in the binary tree
public static int getCount(Node root) {
if (root == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
int count = 1;
while(! queue.isEmpty()) { Node cur = queue.poll();if(cur.left ! =null) {
queue.add(cur.left);
count ++;
}
if(cur.right ! =null) { queue.add(cur.right); count ++; }}return count;
}
Copy the code5.4 Balancing binary trees
5.4.1 definition
For any subtree in a balanced binary tree, the height difference between its left subtree and its right subtree is no more than 1.
5.4.2 graphic
5.4.3 Judging balanced binary trees
Ideas:
- Determine whether the left subtree is a balanced binary tree.
- Determine whether the right subtree is a balanced binary tree.
- Determine whether the absolute value of the height difference between the left and right subtrees is less than or equal to 1.
Note: The code for judging balanced binary trees involves recursive routines of binary trees, see 6.3 for details.
Code: see 6.3.
6. Recursive routines of binary trees
6.1 the content
When solving a binary tree problem, we should take “what kind of information I need to list all the possibilities” as a starting point to think about the problem.
Steps:
- Determine the judgment conditions.
- Identify information structures.
This routine is very useful in solving the difficult problem of binary tree, and can solve all tree DP problems! It’s just a difficult list of possibilities.
Including the following “judgment balance binary tree”, “judgment search binary tree” and other problems, are tree DP problems.
The tree DP question is also the most difficult question about binary tree in the interview.
Note:
This routine does not solve all binary tree problems, but it can solve most of them. Binary tree problems that cannot be solved by this routine are often very troublesome, and the solutions of such problems are usually violent and cannot be optimized. (For example, to find the median of the entire binary tree, even if I get the median of the left subtree and the median of the right subtree, it doesn’t make any sense for me to find the median of the entire subtree.)
As long as the problem can be solved through the left and right subtrees to obtain information, and then adjust the information of the current entire subtree through the information of the left and right subtrees, and then solve the problem of the whole tree, this routine can be used.
6.2 Code Structure
// Information structure
static class Info {... }// Interface function, return value type and method name depending on the problem
public static xxx xxx(Node root) {... }// Auxiliary procedure function
public static Info process(Node root) {
// The return value of base case depends on the problem
if (root == null) {
return xxx;
}
// Collect information about left and right subtrees
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
// Process information about the current subtree.// Returns information about the current subtree
return new Info(xxx)
}
Copy the code6.3 Case Analysis
5.4.3 “Judging whether a tree is a balanced binary tree” was analyzed to describe the recursive routine of binary trees.
The first thing we need to know is when do we balance a binary tree?
For any node, the depth difference between its left subtree depth and its right subtree depth is no more than 1.
Suppose, the current node x is the root of the subtree, I want to determine whether the subtree is a balanced binary tree, how to list the possibilities? This organization of possibilities is based on the fact that you can ask for information from the left subtree of node X, and you can ask for confidence from the right subtree of node X, how do you list possibilities?
First, determine the judgment conditions.
In this case, if the subtree is a balanced binary tree, three conditions are required:
- The left subtree of node X is a balanced binary tree.
- The right subtree of node X is a balanced binary tree.
- The depth difference between the left and right subtrees of node X is no more than 1.
By permutations and combinations, we can make a list of all the possibilities, and we can figure out what’s going on.
Secondly, the information structure is determined.
So, we can determine what we need to know about the left and right subtrees.
In this case, we determine that both the left and right subtrees need information about balance and depth. The requirements for the left and right trees are the same.
Code:
// Information structure
static class Info {
boolean isBBT;
int depth;
R(boolean isBBT, int depth) {
this.isBBT = isBBT;
this.depth = depth; }}public static boolean isBBT(Node root) {
return process(root).isBBT;
}
public static Info process(Node root) {
if (root == null) {
return new Info(true.0);
}
// Get information about the left and right subtrees
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
// Height of the current subtree
int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
boolean isBBT = false;
// Check whether the current node is balanced and the height difference between the left and right subtrees is less than 1
if (leftInfo.isBBT && rightInfo.isBBT && Math.abs(leftInfo.depth - rightInfo.depth) <= 1) {
isBBT = true;
}
// Returns information about the current subtree
return new Info(isBBT, depth);
}
Copy the code6. The interview questions
6.1 Maximum Width of a binary tree
Find the maximum width of a binary tree.
Ideas:
On the basis of binary tree width first traversal, the mechanism of recording the width of each layer is added, and at the same time, a maximum width is compared layer by layer.
The mechanism for recording the width of each layer is mainly reflected in:
- Use two variables to record the current layer and the number of nodes of the current layer respectively.
- Use HashMap to record the number of layers that each node belongs to.
If the current number of layers is inconsistent with the number of layers to which the current traversal node belongs, it indicates that the traversal of the current layer is over and the leftmost node of the next layer has been traversed. In this case, the total number of nodes recorded in the current layer can be counted, and the same is true for other layers.
Code:
public static int getMaxBreadth(Node root) {
if (root == null) {
return -1;
}
/ / the current layer
int curLayer = 1;
// Number of nodes in the current layer
int curLayerNodesNum = 0;
// The number of nodes in the widest layer
int broadestLayerNodesNum = Integer.MIN_VALUE;
// Secondary table, used to record the number of layers of each node
HashMap<Node, Integer> map = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// The number of layers of the root node is recorded in the table
map.put(root, 1);
// The queue ends when it is empty
while(! queue.isEmpty()) { Node cur = queue.poll();// Get the current node layer
int curNodeLayer = map.get(cur);
// Check whether the node is in the current layer
if (curNodeLayer == curLayer) {
curLayerNodesNum ++;
} else {
// Compare with the current maximum number of nodes in the widest layer to find a larger node
broadestLayerNodesNum = Math.max(broadestLayerNodesNum, curLayerNodesNum);
// The current layer goes to the next layer
curLayer ++;
// Initializes the number of nodes in the next layer
curLayerNodesNum = 1;
}
if(cur.left ! =null) {
queue.add(cur.left);
// The number of layers of the left child node of the current node is recorded in the table
map.put(cur.left, curNodeLayer + 1);
}
if(cur.right ! =null) {
queue.add(cur.right);
// The number of layers of the right child node of the current node is recorded in the table
map.put(cur.right, curNodeLayer + 1); }}// At the end of the loop, the number of nodes in the last layer has not been compared with the number of nodes in the widest layer
return Math.max(broadestLayerNodesNum, curLayerNodesNum);
}
Copy the code6.2 Judging the full binary tree
Determine whether a tree is a full binary tree.
Ideas:
Recursive routines using binary trees.
The judgment conditions are: there is no judgment condition for this problem, only need to collect the depth of the subtree and sum up the points. Finally, the full binary tree formula is used for unified judgment.
The information structure is: [Depth of current tree, total number of nodes of current tree]
Code:
static class Info {
// Tree depth
int depth;
// The total number of nodes in the tree
int count;
public Info(int depth, int count) {
this.depth = depth;
this.count = count; }}public static boolean isFBT(Node root) {
Info info = process(root);
int depth = info.depth;
int count = info.count;
// return count == (int) Math.pow(2, depth) - 1;
return count == (1 << depth) - 1;
}
public static Info process(Node root) {
if (root == null) {
return new Info(0.0);
}
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
// The current tree depth
int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
// Total number of nodes in the current tree
int count = leftInfo.count + rightInfo.count + 1;
return new Info(depth, count);
}
Copy the code6.3 Judging binary Tree Search
Determine if a tree is a search binary tree.
Ideas:
Recursive routines using binary trees.
This problem is slightly different from judging a balanced binary tree, because the requirements for the left and right subtrees of a balanced binary tree are the same, so the information structure is easy to determine. In this case, the requirements of the left and right subtrees are different, so the information structure needs to obtain the complete set of information required by the left and right subtrees.
The judgment conditions are:
- The left subtree of node X is a search binary tree.
- The right subtree of node X is a search binary tree.
- The maximum keyword of the left subtree of node X is < x.
- The minimum keyword of the right subtree of node X > x.
The information structure is: [whether search binary tree, the maximum keyword of the current tree, the minimum keyword of the current tree]
Code:
// Information structure
static class Info {
// Whether the current tree is a search binary tree
boolean isSBT;
// The largest keyword in the current tree
int maxValue;
// The smallest keyword in the current tree
int minValue;
public R(boolean isSBT, int maxValue, int minValue) {
this.isBST = isSBT;
this.maxValue = maxValue;
this.minValue = minValue; }}public static boolean isSBT(Node root) {
return process(root).isSBT;
}
public static Info process(Node root) {
if (root == null) {
return null;
}
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
boolean isSBT = true;
// Initializes the value as its own keyword
int maxValue = root.value;
int minValue = root.value;
// Assign the maximum and minimum keyword from the left and right subtrees
if(leftInfo ! =null) {
maxValue = Math.max(leftInfo.maxValue, maxValue);
minValue = Math.min(leftInfo.minValue, minValue);
}
if(rightInfo ! =null) {
maxValue = Math.max(rightInfo.maxValue, maxValue);
minValue = Math.min(rightInfo.minValue, minValue);
}
// If the left subtree exists, the left subtree is not BST or the current node's keyword is less than the maximum keyword of the left subtree
if(leftInfo ! =null&& (! leftInfo.isSBT || leftInfo.maxValue >= root.value)) { isSBT =false;
}
// If the right subtree exists, the right subtree is not BST or the key of the current node is greater than the minimum key of the right subtree
if(rightInfo ! =null&& (! rightInfo.isSBT || rightInfo.minValue <= root.value)) { isSBT =false;
}
return new Info(isSBT, maxValue, minValue);
}
Copy the codeNote:
In the code for this problem, the base case in the process method should return new R(true, XXX, XXX) according to the binary tree recursion, but the handling of minValue and maxValue is tricky, and assigning any value feels inappropriate. At this point, null can be returned, but note that null needs to be conditional at call time.
6.4 Finding the lowest common ancestor
Title: Given two nodes in a binary tree, node1 and node2, find their lowest common ancestor node.
Note: The lowest common ancestor node is the first node above node1 and node2 to converge.
6.4.1 General solution
Construct a HashMap as the parent node table of the entire tree, storing the corresponding relationship between each node in the tree and its parent node (the parent node of the root node is itself). It then builds a HashSet that stores all nodes in the chain from Node1 to the root, and then stores all nodes in the chain from Node2 to the root. Taking advantage of the non-repeatability of the elements in a HashSet, when a node in the chain from Node2 to root causes a HashSet element conflict while being stored, that node is the lowest common ancestor node.
Code:
public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null) {
return null;
}
HashMap<Node, Node> map = new HashMap<>();
// The root node enters the table, and its parent is set to itself
map.put(root, root);
// Add other nodes to the table
process(root, map);
HashSet<Node> set = new HashSet<>();
// The root goes into the secondary container first
set.add(root);
// Add node1 to the container for all nodes in the root node chain
Node cur = node1;
while(cur ! = map.get(cur)) { set.add(cur); cur = map.get(cur); }// Add node2 to all nodes in the root node chain
cur = node2;
while (true) {
// Nodes are bound to collide and return
if (set.contains(cur)) {
returncur; } set.add(cur); cur = map.get(cur); }}public static void process(Node root, HashMap<Node, Node> map) {
if (root == null) {
return ;
}
process(root.left, map);
process(root.right, map);
// Add the left and right child nodes to the table
if(root.left ! =null) {
map.put(root.left, root);
}
if(root.right ! =null) { map.put(root.right, root); }}Copy the code6.4.2 Optimized solution
Ideas:
According to the question, there are only three things that can happen:
- Node1 is the lowest common ancestor node for Node2.
- Node2 is the lowest common ancestor node for Node1.
- Node1 and Node2 are not each other’s lowest common ancestor nodes.
All structural relations can be divided into two categories:
- The lowest common ancestor of both nodes is one of them (case 1,2).
- The two nodes are not each other’s lowest common ancestor (case 3).
Code:
public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
if (root == null || root == node1 || root == node2) {
return root;
}
Node left = lowestCommonAncestor(root.left, node1, node2);
Node right = lowestCommonAncestor(root.right, node1, node2);
if(left ! =null&& right ! =null) {
return root;
}
returnleft ! =null ? left : right;
}
Copy the codeAnalysis:
If a subtree has neither node1 nor node2, then null must be returned.
If a subtree has node1 and node2, and one of the nodes is the root of the subtree, the node as the root is returned.
If a subtree has node1 and node2, and neither node is the root of the subtree, the node where the two nodes first converge is returned.
6.5 Finding a Successor Node
Title: There is now a new binary tree node type as follows:
public class Node {
int value;
Node left;
Node right;
Node parent;
}
Copy the codeThis structure differs from the classical binary tree node structure in that there is a parent pointer to the parent node.
Suppose you have a binary tree of nodes of this type, where each Node’s parent pointer correctly points to its parent and the head Node’s parent points to null. Given a node in the binary tree, find its successors.
The time complexity must be less than O(N).
Note:
-
Successor node: In a binary tree traversal sequence, the next node of a node is called the successor of a node.
-
Precursor node: In a middle-order traversal sequence of a binary tree, the preceding node of a node is called the precursor node of a node.
Analysis:
The time complexity is less than O(N), which means that the successor node cannot be found using the method of viewing the sequence in order.
We defined the distance of a single pointer to be 1.
As shown in the figure, the successor of node D is node B, and the distance between the two nodes in the tree is 1. Node D can find node B directly through parent. The next node of E is NODE A, the distance between the two nodes in the tree is 2, and node E can find node A twice through the parent address.
We assume that if any node has a pointer to the parent node, and if Y node is the successor of X node, and the distance between the two nodes is K, can we reduce the time complexity to O(K), instead of traversing all nodes to get the middle-order traversal sequence.
Therefore, in theory, a node can find its successor only by asking the parent to address with a specified number of distances. Is there any possibility of optimization? Then we need to consider the question, how can the successors of a node be found structurally?
Structurally, there are only three possibilities:
-
If an X node has a right subtree, the successor of the X node is the leftmost node of its right subtree.
-
If the X node has no right child tree, then it starts at the X node and traverses upwards. If the parent node addressed is the left child of the parent node, then the parent node of the ancestor node is the successor node of the X node (for the successor node, X node is the rightmost node in its left child tree).
-
If the X node is the rightmost node of the entire tree, then the node has no descendants and is null.
Code:
public static Node findSuccessorNode(Node root, Node target) {
if (root == null) {
return null;
}
Node cur = target.right;
// The target node has a right subtree
if(cur ! =null) {
while(cur.left ! =null) {
cur = cur.left;
}
return cur;
}
// The target node has no right subtree
else {
cur = target;
while(cur.parent ! =null) {
if (cur == cur.parent.left) {
return cur.parent;
}
cur = cur.parent;
}
// If the node is the rightmost node of the entire tree, the suffix node is null
return null; }}Copy the code6.6 Origami problem
Topic:
Place a piece of paper vertically on a table and fold it in half from the bottom to the top once, making a crease and then unrolling it. The crease is concave.
If from the bottom of the paper to the top of the continuous fold 2 times, after pressing the crease to expand, at this time there are 3 creases, from top to bottom are concave creases, concave creases, protruding creases.
Given an input parameter N, which indicates that the strip is folded consecutively N times from bottom to top, print the directions of all creases from top to bottom, with concave creases as down and convex creases as up.
Such as:
If N is 1, the system prints down
If N is 2, down down up is displayed
Analysis:
First look at the crease condition of three folds:
-
After the first fold, there’s a concave crease.
-
After the second fold, on both sides of the 1 crease, there are new stripes, concave creases on the top, convex creases on the bottom.
-
After the third fold, on each of the two creases, there are new stripes, concave creases on the top, convex creases on the bottom.
A rule can be found: the new concave crease is always above the previous adjacent crease, and the new convex crease is always below the previous adjacent crease.
Therefore, the results of creases can be recursively simulated into a binary tree whose root nodes are concave creases, each left subtree whose root nodes are concave creases, and each right subtree whose root nodes are convex creases.
Printing the crease from top to bottom is a middle-order traversal of the binary tree.
Code:
public static void paperFolding(int N) {
// The first crease is down
process(N, 1.true);
}
/ * * *@paramN Number of folds -- depth of binary tree *@paramDepth Depth of a node *@paramDirection Direction of the crease. True: Down; false: Up */
public static void process(int N, int depth, boolean direction) {
if (depth > N) {
return ;
}
// The left child is down
process(N, depth + 1.true);
System.out.print(direction ? "down " : "up ");
// All the children are up
process(N, depth + 1.false);
}
Copy the code