Classification brush algorithm, persist, progress!
Line reference: github.com/youngyangya…
Hello everyone, I take the output blog to urge themselves to brush the third, this section we brush binary tree, binary tree related topics in the interview is very high frequency, and there are many in the force button, there are hundreds of, don’t panic, we step by step. My article is very long, you keep it.
Binary tree foundation
Binary tree is a common data structure. Before starting to brush binary tree, let’s briefly understand some basic knowledge of binary tree. For more detailed knowledge about data structures, you are advised to learn Data Structures and Algorithms.
What is a binary tree
A binary tree is a tree with at most two subtrees per node.
There are two main forms of binary tree: full binary tree and complete binary tree.
-
Full binary tree: if a binary tree has only nodes of degree 0 and degree 2, and the nodes of degree 0 are on the same level, then the binary tree
A fork tree is a full binary tree. The number of nodes in a full binary tree of depth K is 2^k^ -1.
-
Complete binary tree: only the degree of the lowest two nodes can be less than 2, and the nodes of the lowest layer are concentrated in the leftmost positions of the layer, then this binary tree is called complete binary tree.
We can see that a full binary tree is a complete binary tree, but a complete binary tree is not necessarily a full binary tree.
Binary search tree
Binary search tree, also known as binary search tree, binary sort tree, is a kind of ordered binary tree. It follows the rules of small on the left and big on the right:
- If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.
- If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
- Its left and right subtrees are binary search trees respectively
Binary tree storage structure
Similar to linear tables, binary trees can be stored in two ways: sequential storage and chain storage.
Sequential storage is to store the numbers of all the elements in the binary tree in the corresponding positions of the one-dimensional array, which is more suitable for storing the full binary tree.
Since the sequential storage structure is used to store the general binary tree, a large amount of storage space is wasted.
Binary tree node
We have seen the chain storage of binary trees above, and notice that each node is made up of three parts, the left child, the data, and the right child.
Let’s define the nodes of a binary tree:
/ * * *@Author: Three points of evil *@Date: 2021/6/8
* @Description: * * /
public class TreeNode {
int val; / / value
TreeNode left; / / the left subtree
TreeNode right; / / right subtree
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right; }}Copy the codeBinary tree traversal
There are two main traversal methods for binary trees:
-
Depth-first traversal: Go deep first, then go back when you reach the leaf node.
-
Breadth-first traversal: Go through layer by layer.
Then, the following traversal methods can be further expanded from depth-first traversal and breadth-first traversal:
-
Depth-first traversal
- Sequential traversal (recursion, iteration)
- Middle order traversal (recursive method, iterative method)
- Post-order traversal (recursive method, iterative method)
-
Breadth-first traversal
- Hierarchical traversal (iterative method)
We are familiar with the root, left and right traversal, which refers to the order of root nodes:
- Foreorder traversal: root left and right
- Middle order traversal: left root right
- Post-order traversal: left and right roots
A more memorable way of saying it is first root traversal, middle root traversal, and last root traversal is more obvious.
Let’s look at an example:
There are two ways to achieve the algorithm:
- Recursion: The tree itself is a kind of data structure with recursive properties, using recursion to achieve depth-first traversal is very convenient.
- Iteration: Iteration is done with the help of other data structures, such as stacks.
Now that we’ve covered some of the basics of binary trees, let’s face it with LeetCode!
Depth-first traversal base
Recursive basis
Binary trees are naturally recursive data structures, so let’s touch on recursion briefly.
Recursion has three main elements:
-
Arguments and return values of recursive functions
To determine which parameters need to be processed in the recursive process, add this parameter to the recursive function, and determine the return type of the recursive function by knowing what the return value of each recursion is.
-
Termination Conditions:
Recursion requires attention to the termination condition, and if the termination condition or termination condition is not written correctly, the operating system’s stack will overflow.
-
A single layer of recursive logic
Determine the logic for a single level of recursion, in which the recursive process is repeated by calling itself.
Ok, so let’s get started!
LeetCode144. Antecedent traversal of binary trees
So let’s start with a binary tree traversal.
☕ Title: LeetCode144. Antecedent traversal of binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: Simple
📕 description: Gives you the root node of the binary tree, root, and returns a pre-traversal of its node values.
💡 ideas:
Recursive traversal before order
We looked at the three elements of recursion before, and then we started to use recursion to perform the forward traversal of the binary tree:
- Determine the parameters and return values of the recursive function: Because we want to print the value of the preceding traversal node, we need to pass the List in the parameters to store the value of the node. To pass in the value of the node, you need the node, so the parameters of the recursive function are determined; Since the node values are already in the List, the recursive function returns void and looks like this:
void preOrderRecu(TreeNode root, List<Integer> nodes)
Copy the code- Determine termination conditions: Recursion is also very simple, if the current traversal node is empty, return directly, code like this:
// Recursive end condition
if (root == null) {
return;
}
Copy the code- Determine the logic of single-layer recursion: preorder traversal is the order of the left and right sides of the root, so in the logic of single-layer recursion, first take the value of the root node, then recurse the left and right subtrees, the code is as follows:
// Add the root node
nodes.add(root.val);
// recursive left subtree
preOrderRecu(root.left, nodes);
// Recursive right subtree
preOrderRecu(root.right, nodes);
Copy the codeLet’s look at the complete code for binary tree traversal:
/** * binary tree traversal **@param root
* @return* /
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
preOrderRecu(root, nodes);
return nodes;
}
/** * the binary tree recursively traverses **@param root
* @param nodes
*/
void preOrderRecu(TreeNode root, List<Integer> nodes) {
// Recursive end condition
if (root == null) {
return;
}
// Add the root node
nodes.add(root.val);
// recursive left subtree
preOrderRecu(root.left, nodes);
// Recursive right subtree
preOrderRecu(root.right, nodes);
}
Copy the codeUnit tests:
@Test
public void preorderTraversal(a) {
LeetCode144 l = new LeetCode144();
// Build a binary tree
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
root.left = node1;
node1.right = node2;
// binary tree traversal first
List<Integer> nodes = l.preorderTraversal(root);
nodes.stream().forEach(n -> {
System.out.print(n);
});
}
Copy the codeComplexity:
- 🚗 Time complexity: O(n), where n is the number of nodes in the binary tree.
Recursion is easy for those who know it, but not for those who don’t. Isn’t that easy to understand? 😂
So let’s do the iterative method, which is a little bit more difficult.
Iterative method before traversal
The principle of iterative method is to introduce a new data structure for storing the nodes traversed.
The process of recursion is to keep going to the left, and when the recursion ends, nodes are added. Now with iteration, we need to store the nodes ourselves with a data structure.
So what data structure is appropriate? The natural thing to think about is stacks.
The core of iteration method is: with the help of stack structure, simulate the process of recursion, need to pay attention to when out of the stack, when to visit the node.
If the right subtree is not empty, the right subtree is pushed. If the right subtree is not empty, the right subtree is pushed.
Ps: Notice that the way we write it is to store elements into the list before the stack operation, which is mainly used to find the right subtree.
Iteration and recursion are essentially the same thing, but in recursion the stack is managed implicitly by the virtual machine.
/** * binary tree forward traversal - iterative method **@param root
* @return* /
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
// Use linked lists as stacks
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root! =null| |! stack.isEmpty()){while(root! =null) {/ / root
nodes.add(root.val);
stack.push(root);
/ / left
root=root.left;
}
/ / out of the stack
root=stack.pop();
/ / right
root=root.right;
}
return nodes;
}
Copy the code- 🚗 Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is traversed exactly once.
LeetCode94. Middle order traversal of binary trees
☕ Title: LeetCode94. Middle order Traversal of binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: Simple
📕 description: Gives you the root node of the binary tree, root, and returns a pre-traversal of its node values.
- Sequential traversal in recursion
We have already performed a large binary tree traversal recursively, which is similar to the middle traversal, except that the order of the root nodes is placed in the middle.
/** * order traversal - recursive **@param root
* @param nodes
*/
void inOrderRecu(TreeNode root, List<Integer> nodes) {
if (root == null) {
return;
}
// recursive left subtree
inOrderRecu(root.left, nodes);
/ / the root node
nodes.add(root.val);
// Recursive right subtree
inOrderRecu(root.right, nodes);
}
Copy the code-
Sequential traversal in iterative method
In the iterative method, the stack is also used to hold nodes.
Sequential traversal in iterative method is similar to pre-sequential traversal, but the timing of accessing nodes is different:
- A pre-traversal requires accessing the root before each left turn
- In order to traverse the stack first, in the time to access the stack
Push all the left children of the node onto the stack, and then unstack the node. When unstack the value of the node is put into the List. If the right child of the node is not empty, the right child is processed.
/** * order traversal - iteration **@param root
* @return* /
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
// Use linked lists as stacks
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root ! =null| |! stack.isEmpty()) {// Iterate over the left subtree
while(root ! =null) {
stack.push(root);
root = root.left;
}
// Remove the node from the stack
root = stack.pop();
// Add the removed node
nodes.add(root.val);
/ / right subtree
root = root.right;
}
return nodes;
}
Copy the codeLeetCode145. Post-order traversal of binary trees
☕ Title: 145. Postordered traversal of binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: Simple
📕 Description: Given a binary tree, return its sequential traversal.
- Recursive order traversal
Recursion, as long as you understand can say so easy!
/** * backorder traversal of binary tree - recursive **@param nodes
* @param root
*/
void postorderRecu(List<Integer> nodes, TreeNode root) {
if (root == null) {
return;
}
// recursive left subtree
postorderRecu(nodes, root.left);
// Recursive right subtree
postorderRecu(nodes, root.right);
/ / root tree
nodes.add(root.val);
}
Copy the code- Sequential traversal after iteration method
Recursive order traversal, you can use a trick, just use the pre-order traversal, pre-order traversal is the root left and right, post-order traversal is the root left and right, we just need to reverse the result of the pre-order traversal, is the root left and right.
If implemented in Java, you can play around with linked lists, and changing a tail to a header has the same effect.
/** * backorder traversal of binary tree - iteration **@param root
* @return* /
public List<Integer> postorderTraversal(TreeNode root) {
// Use linked lists as stacks
Deque<TreeNode> stack = new LinkedList<TreeNode>();
/ / the node
LinkedList<Integer> nodes = new LinkedList<Integer>();
while(root ! =null| |! stack.isEmpty()) {while(root ! =null) {
// Insert a node into a socket
nodes.addFirst(root.val);
// The root node is pushed
stack.push(root);
/ / the left subtree
root = root.left;
}
// Node unstack
root = stack.pop();
/ / right subtree
root = root.right;
}
return nodes;
}
Copy the codeOf course, this is kind of a trick, you say this is not a real post-iterative traversal, a real post-iterative binary tree, it’s not complicated,
The point is:
- Access the root if the right subtree is empty or has already been accessed
- Otherwise, the node needs to be pushed back onto the stack to access its right subtree
/** * binary tree backorder traversal - iteration - general **@param root
* @return* /
public List<Integer> postorderTraversal1(TreeNode root) {
// Use linked lists as stacks
Deque<TreeNode> stack = new LinkedList<TreeNode>();
// Node value store
List<Integer> nodes = new ArrayList<>(16);
// Used to record the previous node
TreeNode pre = null;
while(root ! =null| |! stack.isEmpty()) {while(root ! =null) {
// The root node is pushed
stack.push(root);
/ / the left subtree
root = root.left;
}
// Node unstack
root = stack.pop();
// Check whether the right subtree of the node is empty or has already been accessed
if (root.right == null || root.right == pre) {
// Add a node
nodes.add(root.val);
// Update the visited nodes
pre = root;
// make the next loop go straight out of the next stack
root = null;
} else {
// push it again
stack.push(root);
// Access the right subtreeroot = root.right; }}return nodes;
}
Copy the codeBreadth-first traversal base
LeetCode102. Sequence traversal of binary trees
☕ Title: 102. Sequence traversal of binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: medium
📕 description: I give you a binary tree and ask you to return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).
We have already done depth-first traversal of binary trees using iterative methods, now let’s take a look at breadth-first traversal.
In iterative depth-first traversal, we use the data structure of stack to store nodes. Then what data structure is suitable for the logic of sequential traversal, which is layer by layer?
The answer is the queue.
So what is the idea of sequential traversal?
Using a queue, we store each layer of nodes in the queue. When the layer of storage is finished, we take the nodes out of the queue again. The left and right children are not empty, so we put the left and right children in the queue.
/** * binary tree sequence traversal **@param root
* @return* /
public List<List<Integer>> levelOrder(TreeNode root) {
// Result set
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
// Save the queue for the node
Queue<TreeNode> queue = new LinkedList<>();
// Add the root node
queue.offer(root);
while(! queue.isEmpty()) {// Store the set of nodes in each layer
List<Integer> level = new ArrayList<>(8);
// The size of each layer of the queue must be set first, because the queue is constantly changing
int queueSize = queue.size();
// Walk through the queue
for (int i = 1; i <= queueSize; i++) {
// Fetch the queue node
TreeNode node = queue.poll();
// Add nodes to each layer collection
level.add(node.val);
// If the left child of the current node is not empty, the left child joins the team
if(node.left ! =null) {
queue.offer(node.left);
}
// If the right child is not empty, the right child joins the team
if(node.right ! =null) { queue.offer(node.right); }}// The result combination is added to the result set of each layer
result.add(level);
}
return result;
}
Copy the code- 🚗 Time complexity: each point enters and exits the queue once, so the progressive time complexity is O(n).
Now that the foundation for depth-first and breadth-first traversal of binary trees is complete, let’s take a look at the variations that can be derived from these two traversals.
Breadth-first traversal base – variant
Let’s first look at some problems that have a slight variation on the order traversal.
Finger Offer 32-i. Print binary tree from top to bottom
☕ Title: Finger Offer 32-i. Print binary tree from top to bottom (leetcode-cn.com/problems/co…)
❓ Difficulty: medium
📕 Description: Print each node of the binary tree from top to bottom, and the nodes of the same layer are printed from left to right.
💡 ideas:
So this is a pretty small change.
The zha do?
Just do it!
/** * Prints the binary tree from top to bottom **@param root
* @return* /
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> nodes=new ArrayList<>(64);
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
/ / the root node
queue.offer(root);
while(! queue.isEmpty()) { TreeNode node = queue.poll(); nodes.add(node.val);// The left child enters the team
if(node.left ! =null) {
queue.offer(node.left);
}
// The right child joins the team
if(node.right ! =null) { queue.offer(node.right); }}// Result array
int[] result = new int[nodes.size()];
for (int i = 0; i < nodes.size(); i++) {
result[i] = nodes.get(i);
}
return result;
}
Copy the codeYou don’t have to change a few lines of code.
Finger Offer 32-iii. Print binary tree III from top to bottom
☕ Title: Finger Offer 32-iii. Print binary tree III from top to bottom (leetcode-cn.com/problems/co…)
❓ Difficulty: medium
📕 Description: Implement a function to print a binary tree in glyph order, that is, the first line is printed from left to right, the second line is printed from right to left, the third line is printed from left to right, and so on.
💡 ideas:
The change in this problem is that the odd-numbered layers are printed from left to right, and the even-numbered layers are printed from right to left.
So we need a variable to keep track of the hierarchy.
What data structure can interpolate data from left to right as well as right to left?
We think of bidirectional linked lists.
/** * Indicates Offer 32-iii. Print binary tree III ** from top to bottom@param root
* @return* /
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
/ / the root node
queue.offer(root);
// Record hierarchy
int levelCount = 1;
while(! queue.isEmpty()) {// Current queue size
int queueSize = queue.size();
// Use a bidirectional linked list to store each layer of nodes
LinkedList<Integer> level = new LinkedList<>();
for (int i = 1; i <= queueSize; i++) {
/ / the node
TreeNode node = queue.poll();
// Determine the level
// Odd number, tail
if (levelCount % 2= =1) {
level.addLast(node.val);
}
// Even, head plug
if (levelCount % 2= =0) {
level.addFirst(node.val);
}
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
/ / right child
if(node.right ! =null) { queue.offer(node.right); }}// Add nodes for each layer
result.add(level);
// The level is increased
levelCount++;
}
return result;
}
Copy the codeLeetCode107. Sequence traversal of binary trees II
☕ Title: 107. Sequence traversal of binary trees II (leetcode-cn.com/problems/bi…)
❓ Difficulty: medium
📕 Description: Given a binary tree, return a bottom-up sequence traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)
💡 ideas:
Remember our trick of going through a binary tree sequentially? That’s the same thing, traversing the List, reversing the List, or inserting the set of each level with a List header.
/** * binary tree sequence traversal II **@param root
* @return* /
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// Use a linked list to store results, and use a header to add elements
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
// Insert the root node
queue.offer(root);
while(! queue.isEmpty()) {// Store the set of nodes in each layer
List<Integer> level = new ArrayList<>(8);
// The current queue size needs to be set properly because the queue is constantly changing
int currentQueueSize = queue.size();
// Walk through the queue
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
// Add values to each layer collection
level.add(node.val);
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
/ / right child
if(node.right ! =null) { queue.offer(node.right); }}// Insert a set of nodes at each level
result.addFirst(level);
}
return result;
}
Copy the codeLeetCode199. Right view of binary trees
☕ Title: 199. Right View of binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: medium
📕 Description: Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side in order from top to bottom.
💡 ideas:
That’s easy too, right?
We just need to determine whether the node is the last element of each layer, or whether it joins the set.
How do you know? Remember we maintain a variable of the number of elements per level? Take this judgment.
/** * Right view of binary tree **@param root
* @return* /
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
// The root node joins the queue
queue.offer(root);
while(! queue.isEmpty()) {// Maintain the current queue size
int queueCurrentSize = queue.size();
for (int i = 1; i <= queueCurrentSize; i++) {
// Retrieve the node currently traversed
TreeNode node = queue.poll();
// Check if it is the most right one
if (i == queueCurrentSize) {
// Add node values to the result set
result.add(node.val);
}
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
/ / right child
if(node.right ! =null) { queue.offer(node.right); }}}return result;
}
Copy the codeLeetCode637. Level mean of binary trees
☕ Title: 637. Layer mean values of binary trees (leetcode-cn.com/problems/av…)
❓ Difficulty: Simple
📕 Description: Given a non-empty binary tree, return an array of the average values of nodes at each level.
Sum each layer, divide by the number of nodes, and take the mean.
/** * 637. The average level of binary tree **@param root
* @return* /
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) {
return result;
}
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
/ / the root node
queue.offer(root);
while(! queue.isEmpty()) {int currentQueueSize = queue.size();
// The total value of each layer
double levelSum = 0;
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
/ / accumulation
levelSum += node.val;
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) { queue.offer(node.right); }}/ / the mean
double avg = levelSum / currentQueueSize;
// Add the average value of each layer to the result set
result.add(avg);
}
return result;
}
Copy the codeOrder traversal of leetcode429.n fork tree
☕ Title: Sequence traversal of 429.n tree (leetcode-cn.com/problems/n-…)
❓ Difficulty: medium
📕 Description: Given an n-tree, return a sequential traversal of its node values. (that is, from left to right, layer by layer).
The serialized input to the tree is traversed in order, with each set of child nodes separated by null values (see example).
Similar to the sequential traversal of binary trees, not many trees become n-tree, the idea is similar, except that the enqueuing of left and right child nodes becomes the enqueuing of set of child nodes.
/** * 429@param root
* @return* /
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
/ / the queue
Deque<Node> queue = new LinkedList<>();
/ / the root node
queue.offer(root);
while(! queue.isEmpty()) { List<Integer> level =new ArrayList<>(8);
int currentQueueSize = queue.size();
for (int i = 1; i <= currentQueueSize; i++) {
Node node = queue.poll();
level.add(node.val);
// Check whether the child node is empty and add the child node
if (!node.children.isEmpty()) {
queue.addAll(node.children);
}
}
// Add nodes for each layer
result.add(level);
}
return result;
}
Copy the codeLeetCode515. Find the maximum value in each tree line
☕ Title: 515. Find the maximum value in each tree line (leetcode-cn.com/problems/fi…)
❓ Difficulty: medium
📕 Description: You need to find the maximum value in each row of the binary tree.
💡 ideas:
Define a variable that represents the maximum number at each level.
/** * 515. Find the maximum value in each tree line **@param root
* @return* /
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
/ / the queue
Deque<TreeNode> queue = new LinkedList<>();
/ / the root node
queue.offer(root);
while(! queue.isEmpty()) {int queueSize = queue.size();
/ / Max
Integer max = Integer.MIN_VALUE;
// Iterate over a layer
for (int i = 1; i <= queueSize; i++) {
/ / the node
TreeNode node = queue.poll();
if (node.val > max) {
max = node.val;
}
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
}
result.add(max);
}
return result;
}
Copy the codeLeetCode116. Populates the next right node pointer for each node
☕ Title: 116. Populate the next right node pointer of each node (leetcode-cn.com/problems/po…)
❓ Difficulty: medium
📕 Description: Given a perfect binary tree with all leaf nodes in the same layer, each parent node has two child nodes. Binary trees are defined as follows:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Copy the codePopulate each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.
Initially, all next Pointers are set to NULL.
Advanced:
- You can only use constant level extra space.
- Using recursion is also acceptable, in this case the stack space occupied by the recursive program does not count as additional space complexity.
💡 ideas:
We add a variable to the previous node and make the next of the previous node point to the current node.
/** * 116. Populates the next right node pointer ** for each node@param root
* @return* /
public Node connect(Node root) {
if (root == null) {
return root;
}
/ / the queue
Deque<Node> queue = new LinkedList();
/ / the root node
queue.offer(root);
while(! queue.isEmpty()) {int queueSize = queue.size();
// The previous node
Node pre = null;
for (int i = 0; i < queueSize; i++) {
Node node = queue.poll();
// The first node of each layer
if (i == 0) {
pre = node;
}
// Make next of the node to the left of the preceding dot point to the current node
if (i > 0) {
pre.next = node;
pre = node;
}
/ / the left child
if(node.left ! =null) {
queue.offer(node.left);
}
/ / right child
if(node.right ! =null) { queue.offer(node.right); }}}return root;
}
Copy the codeLeetCode117. Populates the next right node pointer II for each node
☕ Title: 117. Populate the next right node pointer of each node II (leetcode-cn.com/problems/po…)
❓ Difficulty: medium
📕 Description: Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Copy the codePopulate each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.
Initially, all next Pointers are set to NULL.
💡 ideas:
Isn’t it basically the same as the last problem? Except it’s not perfect, but it doesn’t affect the same code.
After doing ten problems in a row that can be solved by one routine, do you instantly feel refreshed and confident? Let’s continue!
Due to the third time and level of the limited, so the next topic to recursive method.
Binary tree properties
LeetCode101. Symmetric binary trees
☕ Title: 101. Symmetric binary trees (leetcode-cn.com/problems/sy…)
❓ Difficulty: Simple
📕 Description: Given a binary tree, check whether it is mirror – symmetric.
💡 ideas:
So the first part of this problem is to figure out, what mirror image is this mirror image?
To determine binary tree symmetry, compare two trees (that is, the left and right subtrees of the root node).
Notice, you’re comparing the elements to the left of T1 to the elements to the right of T2;
And the element to the left of T2 and the element to the right of T1.
All right, so let’s see how this recursion works.
-
Recursive method parameters and return values
-
The return value is symmetric or not, which is Boolean
-
Two subtrees are being compared, so the arguments are left and right subtree nodes
-
-
Termination conditions
- Returns if both Pointers are null
true - Return if one of them is empty
false - Return if the values of the two nodes are not equal
false
- Returns if both Pointers are null
-
Recursive logic
-
Determine whether the right subtree of T1 is symmetric with the left subtree of T2
-
Determine whether the left subtree of T1 is symmetric with the right subtree of T2
And then you have to short-circuit and, and then you have to return true for both to be true
-
Look at the code:
/** * 101. Symmetric binary tree **@param root
* @return* /
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
// Call a recursive function to compare left and right children
return isSymmetric(root.left, root.right);
}
boolean isSymmetric(TreeNode left, TreeNode right) {
// Recursive termination condition
//1. The left and right nodes are empty
if (left == null && right == null) {
return true;
}
// One of the two nodes is empty
if (left == null || right == null) {
return false;
}
// the value of the two nodes is not equal
if(left.val ! = right.val) {return false;
}
// Recurse left child of left node and right child of right node
boolean outSide = isSymmetric(left.left, right.right);
// Recurse the right child of the left node and the left child of the right node
boolean inSide = isSymmetric(left.right, right.left);
// If both are symmetric, the tree is symmetric
return outSide && inSide;
}
Copy the code- 🚗 Time complexity: O(n)
LeetCode104. Maximum depth of binary trees
☕ Title: 104. Maximum depth of binary trees (leetcode-cn.com/problems/ma…)
❓ Difficulty: Simple
📕 Description: Given a binary tree, find its maximum depth.
The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.
Note: Leaf nodes are nodes that have no child nodes.
💡 ideas:
So this is actually similar to a post-order traversal. Recursive left and right subtrees, find the depth of the left and right subtrees, the maximum of which plus the depth of the root node.
Let’s see what the recursion looks like:
-
Input and return parameters
-
The input parameter is the root node of the tree and represents the tree
-
The backparameter is the depth of the tree
-
-
Termination conditions
- If the root node is empty, the tree is empty
-
Single logical
- Find the depth l of the left child root
- Find the depth r of the right subtree
- The maximum depth of the two subtrees plus the root node depth, Max (l.r) + 1
Look at the code:
/** * 104. Maximum depth of binary tree **@param root
* @return* /
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int maxDepth = Math.max(leftDepth, rightDepth) + 1;
return maxDepth;
}
Copy the code- 🚗 Time complexity: O(n)
LeetCode 559. N The maximum depth of the fork tree
☕ Title: 559. maximum depth of N fork trees (leetcode-cn.com/problems/ma…)
❓ Difficulty: Simple
📕 Description: Given an n-fork tree, find its maximum depth.
The maximum depth is the total number of nodes along the longest path from the root node to the farthest leaf node.
N fork tree input is serialized in sequential traversal, with each set of child nodes separated by null values (see example).
💡 ideas:
As with the previous idea, the code looks like this:
/** * 559@param root
* @return* /
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int maxDepth = 0;
for (int i = 0; i < root.children.size(); i++) {
int childrenDepth = maxDepth(root.children.get(i));
if(childrenDepth > maxDepth) { maxDepth = childrenDepth; }}return maxDepth + 1;
}
Copy the code- 🚗 Time complexity: Each node is traversed once. Therefore, the time complexity is O(N), where NNIs the number of nodes.
LeetCode111. Minimum depth of binary tree
☕ Title: 111. Minimum depth of binary trees (leetcode-cn.com/problems/mi…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
** Note: ** leaf nodes refer to nodes that have no child nodes.
💡 ideas:
At first glance, it looks like, isn’t it the same as the maximum depth of a binary tree?
On closer inspection, something was wrong.
The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
Is to the nearest leaf node. If the subtree is empty, there are no leaf nodes.
So consider this in our single-layer logic, which looks like this:
/** * 111. The minimum depth of binary tree **@param root
* @return* /
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
/ / the left subtree
int leftDepth = minDepth(root.left);
/ / the left subtree
int rightDepth = minDepth(root.right);
// The left subtree is empty
if (root.left == null&& root.right ! =null) {
return rightDepth + 1;
}
// The right subtree is empty
if (root.right == null&& root.left ! =null) {
return leftDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
Copy the code- 🚗 Time complexity: O(n)
LeetCode222. Number of nodes in a complete binary tree
☕ Title: 222. Number of nodes in complete binary trees (leetcode-cn.com/problems/co…)
❓ Difficulty: Simple
📕 description:
Given the root node of a complete binary tree, find the number of nodes in the tree.
A complete binary tree is defined as follows: In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be filled, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, this layer contains 1 to 2h nodes.
** Advanced: ** Traversing the tree to count nodes is a simple O(n) time complexity solution. Can you design a faster algorithm?
💡 ideas:
Recursive method:
It’s pretty easy to use recursion. Left and right subtree recursion plus the root node.
/** * 222. Number of nodes in complete binary tree **@param root
* @return* /
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = countNodes(root.left);
int rightCount = countNodes(root.right);
return leftCount + rightCount + 1;
}
Copy the code- 🚗 Time complexity: O(n).
Using full binary tree properties:
Let’s recall what a complete binary tree is: a binary tree is called a complete binary tree if at most the lowest two nodes of the tree can have a degree less than 2, and all the nodes of the lowest layer are concentrated in the leftmost positions of the layer.
There are two cases of complete binary trees:
-
Full binary tree
-
The last layer is not full
In the first case, the number of nodes =2^k-1 (k is the depth of the tree and the depth of the root node is 0).
In the second case, we recurse to the left child and the right child, and if we recurse to a certain depth there must be a full binary tree with either the left child or the right child, so we can use 2 to the k minus 1.
As long as the tree is not a full binary tree, recurse to the left and right child, until the full binary tree, using the formula to calculate the number of nodes in the subtree.
The code is as follows:
/** * 222. The number of nodes in a complete binary tree - using the complete binary tree feature **@param root
* @return* /
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
/ / the left child
TreeNode left = root.left;
/ / right child
TreeNode right = root.right;
int leftHeight = 0, rightHeight = 0;
// Find the left subtree depth
while(left ! =null) {
left = left.left;
leftHeight++;
}
// Find the right subtree depth
while(right ! =null) {
right = right.right;
leftHeight++;
}
// full binary tree
if (leftHeight == rightHeight) {
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
Copy the code- 🚗 Time complexity: O(logn * logn)
- 🏠 Space complexity: O(logn)
LeetCode110. Balanced binary trees
☕ Title: 110. Balanced binary trees (leetcode-cn.com/problems/ba…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, determine whether it is a highly balanced binary tree.
In this case, a highly balanced binary tree is defined as:
The absolute value of the height difference between the left and right subtrees of each node in a binary tree is no more than 1.Copy the code
💡 ideas:
Earlier, we did a problem: 104. The maximum depth of a binary tree.
A balanced binary tree is defined as a binary tree where the absolute value of the height difference between the left and right subtrees of each node is no more than 1.
So we have the idea of using the way of pre-order traversal to determine whether a node and the left and right subtrees of the node are balanced.
The code is as follows:
/** * 110. Balanced binary tree **@param root
* @return* /
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
// Left subtree height
int leftDepth = depth(root.left);
// Right subtree height
int rightDepth = depth(root.right);
// The current node
boolean isRootBalanced = Math.abs(leftDepth - rightDepth) <= 1;
// recursive left subtree
boolean isLeftBalanced = isBalanced(root.left);
// Recursive right subtree
boolean isRightBalaced = isBalanced(root.right);
/ / balance
return isRootBalanced && isLeftBalanced && isRightBalaced;
}
/** * Get the subtree height **@param root
* @return* /
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
// Left subtree height
int leftDepth = depth(root.left);
// Right subtree height
int rightDepth = depth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
Copy the code- 🚗 Time complexity: the time complexity of obtaining the height of the subtree is O(n), and the judgment of balance requires constant recursion to the left and right subtrees, so the time complexity is O(n²).
It’s a slightly more time intensive way, it’s a top-down way of judging.
There’s another way to do it, which is to go from the bottom up, which is kind of like a backward binary tree traversal.
/** * 110. Balanced binary tree - from bottom up **@param root
* @return* /
public boolean isBalanced(TreeNode root) {
returnhelper(root) ! = -1;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
// Imbalance returns -1 directly
/ / the left subtree
int left = helper(root.left);
// The left subtree is unbalanced
if (left == -1) {
return -1;
}
/ / right subtree
int right = helper(root.right);
// The right subtree is unbalanced
if (right == -1) {
return -1;
}
// If the left and right subtrees are balanced binary trees
// Check whether the height difference between left and right subtrees is less than 1
if (Math.abs(left - right) > 1) {
return -1;
}
// Returns the maximum height of a node in the binary tree
return Math.max(left, right) + 1;
}
Copy the code- 🚗 Time complexity: Each node is traversed only once from bottom to top, so the time complexity is O(n).
LeetCode404. Sum of left leaves
☕ Title: 404. Sum of left leaves (leetcode-cn.com/problems/su…)
❓ Difficulty: Simple
📕 description:
Computes the sum of all left leaves of a given binary tree.
💡 ideas:
This is a dangerous problem, but it’s not difficult, but the point is to figure out what is the left leaf node?
-
First of all, this node has to be the left child of the parent node,
-
Second, the node has to be a leaf node.
Once this is clear, it is a pre-traversal, the code is as follows:
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
// Check whether the left child of the root node is the left leaf
if(root.left ! =null && root.left.left == null && root.left.right == null) {
sum = root.left.val;
}
// Recurse left and right subtrees
return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
Copy the code- 🚗 Time complexity: O(n).
LeetCode513. Find the value in the lower left corner of the tree
☕ Title: 513. Find the value in the lower left corner of the tree (leetcode-cn.com/problems/fi…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, find the leftmost value in the last row of the tree.
💡 ideas:
We have already done ten breadth-first traversal problems, so we don’t need to talk about them here. Here is the code:
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
int bottomLeftValue = 0;
// Save the queue for the node
Queue<TreeNode> queue = new LinkedList<>();
// Add the root node
queue.offer(root);
while(! queue.isEmpty()) {int currentSize = queue.size();
// Fetch the node from the queue
for (int i = 0; i < currentSize; i++) {
// Fetch the node in the queue
TreeNode node = queue.poll();
// The leftmost node of each layer
if (i == 0) {
/ / assignment
bottomLeftValue = node.val;
}
// The left child of the current node joins the queue
if(node.left ! =null) {
queue.offer(node.left);
}
// The child on the right of the current node joins the queue
if(node.right ! =null) { queue.offer(node.right); }}}return bottomLeftValue;
}
Copy the code- 🚗 Time complexity: O(n).
Binary tree path problem
LeetCode257. All paths to a binary tree
☕ Title: 257. All paths to binary trees (leetcode-cn.com/problems/bi…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, return all paths from the root node to the leaf node.
Note: Leaf nodes are nodes that have no child nodes.
💡 ideas:
We can do this in depth-first traversal — preorder traversal, recursion, which we’ve already written.
But this problem isn’t just recursion, it hides backtracking.
Analogies to our ordinary walking, if we want to walk all the way from one intersection, how should we walk?
That is, we go to the end of one corner, then go back to the last corner and go in the other direction.
For this problem, the backtracking diagram is as follows:
Take a look at the code:
/ * * *@return java.util.List<java.lang.String>
* @Description: all paths to the binary tree - back to the first version *@authorThree points *@date2021/7/14 8:28 * /
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
LinkedList path = new LinkedList();
traversal(root, path, result);
return result;
}
/ * * *@return void
* @Description: traversal *@authorThree points *@date 2021/7/14 8:29
*/
void traversal(TreeNode current, LinkedList path, List<String> result) {
path.add(current.val);
// Leaf node
if (current.left == null && current.right == null) {
StringBuilder sPath = new StringBuilder();
for (int i = 0; i < path.size() - 1; i++) {
sPath.append(path.get(i));
// Don't forget the arrow
sPath.append("- >");
}
sPath.append(path.get(path.size() - 1));
result.add(sPath.toString());
return;
}
// recursive left subtree
if(current.left ! =null) {
traversal(current.left, path, result);
/ / back
path.removeLast();
}
// Recursive right subtree
if(current.right ! =null) {
traversal(current.right, path, result);
/ / backpath.removeLast(); }}Copy the codeIt is possible to simplify, but backtracking is hidden:
/ * * *@return java.util.List<java.lang.String>
* @Description: 257. All paths to the binary tree * https://leetcode-cn.com/problems/binary-tree-paths/ *@authorThree points *@date2021/7/11 10:11 * /
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
traversal(root, "", result);
return result;
}
/ * * *@return void
* @Description: traversal *@authorThree points *@date2021/7/11 10:10 * /
void traversal(TreeNode current, String path, List<String> result) {
path += current.val;
// Leaf node
if (current.left == null && current.right == null) {
// Add the path to the result
result.add(path);
return;
}
// recursive left subtree
if(current.left ! =null) {
traversal(current.left, path + "- >", result);
}
// Recursive right subtree
if(current.right ! =null) {
traversal(current.right, path + "- >", result); }}Copy the code- 🚗 Time complexity: O(n²), where n indicates the number of nodes. In depth-first search, each node will be visited once and only once. Each time, the path variable will be copied and constructed. The time cost is O(n), so the time complexity is O(n^2).
LeetCode112. Sum of paths
☕ Title: 112. Sum of paths (leetcode-cn.com/problems/pa…)
❓ Difficulty: Simple
📕 description:
You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.
A leaf node is a node that has no children.
💡 ideas:
Now that the path problem has started, let’s do a couple of steps to solidify it.
Same idea: recursive traversal + backtracking
The code is as follows:
/ * * *@return boolean
* @Description:
* @authorThree points *@date2021/7/13 8:34 * /
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum - root.val);
}
/ * * *@return boolean
* @Description: traversal *@authorThree points *@date2021/7/14 21:22 * /
boolean traversal(TreeNode current, int count) {
// Termination conditions
if (current.left == null && current.right == null && count == 0) {
// Leaf node, and the count is 0
return true;
}
if (current.left == null && current.right == null) {
// Leaf node
return false;
}
/ / the left subtree
if(current.left ! =null) {
count -= current.left.val;
if (traversal(current.left, count)) {
return true;
}
// Backtrace, undo the result of processing
count += current.left.val;
}
/ / right subtree
if(current.right ! =null) {
count -= current.right.val;
if (traversal(current.right, count)) {
return true;
}
count += current.right.val;
}
return false;
}
Copy the codeSimplify a wave as follows:
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum);
}
private boolean traversal(TreeNode root, int count) {
if (root == null) {
return false;
}
// Find a path that satisfies the condition
if (root.left == null && root.right == null && count == root.val) {
return true;
}
return traversal(root.left, count - root.val) || traversal(root.right, count - root.val);
}
Copy the code- 🚗 Time complexity: same as the previous problem, O(n²).
LeetCode113. Sum of paths II
☕ Title: 113. Sum of paths II (leetcode-cn.com/problems/pa…)
❓ Difficulty: medium
📕 description:
Given the root node of the binary tree, root, and an integer target and targetSum, find all paths from the root node to the leaf node where the sum of paths is equal to the given targetSum.
A leaf node is a node that has no children.
💡 ideas:
Boy, this is a combination of 257 and 112!
So let’s go recursively and backtrack.
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
/ / the result
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
/ / path
LinkedList<Integer> path = new LinkedList();
traversal(root, path, result, targetSum - root.val);
return result;
}
private void traversal(TreeNode root, LinkedList<Integer> path, List<List<Integer>> result, int count) {
// The root node is placed in the path
path.add(root.val);
// Leaf nodes, and the sum of nodes meets the requirement
if (root.left == null && root.right == null && count == 0) {
// Add a reference to path as result
List<Integer> newPath = new LinkedList<>(path);
// Add a path
result.add(newPath);
return;
}
// If it is a leaf node, return directly
if (root.left == null && root.right == null) {
return;
}
// recursive left subtree
if(root.left ! =null) {
count -= root.left.val;
traversal(root.left, path, result, count);
/ / back
path.removeLast();
count += root.left.val;
}
// Recursive right subtree
if(root.right ! =null) {
count -= root.right.val;
traversal(root.right, path, result, count);
/ / backpath.removeLast(); count += root.right.val; }}Copy the codeLet’s simplify:
/ / the result
List<List<Integer>> result = new ArrayList<>(16);
/ / path
LinkedList<Integer> path = new LinkedList<>();
/ * * *@return java.util.List<java.util.List < java.lang.Integer>>
* @Description: 113. Sum of paths II *@authorThree points *@date 2021/7/12 21:25
*/
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return result;
}
traversal(root, targetSum);
return result;
}
/ * * *@return void
* @Description: depth-first traversal *@authorThree points *@date2021/7/12 22:03 * /
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
/ / the path and
sum -= root.val;
// Add a node
path.offerLast(root.val);
// Reach the leaf node, and the path and meet the requirements
if (root.left == null && root.right == null && sum == 0) {
result.add(new LinkedList<>(path));
}
// recursive left subtree
traversal(root.left, sum);
// Recursive right subtree
traversal(root.right, sum);
/ / back
path.pollLast();
}
Copy the code- 🚗 Time complexity: O(n^2).
LeetCode437. Sum of paths III
☕ Title: 437. Sum of paths III (leetcode-cn.com/problems/pa…)
❓ Difficulty: medium
📕 description:
Given a binary tree, each node contains an integer value.
Find paths and the total number of paths equal to the given value.
The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent to child).
The number of nodes in the binary tree cannot exceed 1000, and the value of the node is an integer ranging from -1000000 to 1000000.
💡 ideas:
This problem doesn’t have to start at the root, and it doesn’t have to end at the leaf, so,
- We’re going to go through each node, we’re going to do an extra recursion
- Get the path that matches the condition, and do not return
The following code, directly on the simplified version, looked at the previous problem, I believe that the original version of recursion + backtracking is also a small case.
/ / the result
int result = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
/ / the root node
traversal(root, targetSum);
// Left subtree recursion
pathSum(root.left, targetSum);
// Right subtree recursion
pathSum(root.right, targetSum);
return result;
}
/ * * *@return void
* @Description: depth-first traversal *@authorThree points *@date2021/7/12 22:03 * /
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
/ / the path and
sum -= root.val;
// Do not need to reach the leaf node, the path and meet the requirements
if (sum == 0) {
// Result added
result++;
}
// recursive left subtree
traversal(root.left, sum);
// Recursive right subtree
traversal(root.right, sum);
}
Copy the code- 🚗 Time complexity: pathSum traverses each node in O(n) and traversal in O(n) so O(n²).
One question — interview question 04.12. Summing up the path (leetcode-cn.com/problems/pa…) It’s basically the same thing as this problem.
Modification and construction of binary tree
LeetCode 106. Construct binary trees by traversing sequences in middle and rear order
☕ Title: 106. Constructing binary trees from middle-order and post-order traversal sequences (leetcode-cn.com/problems/co…)
❓ Difficulty: medium
📕 description:
The binary tree is constructed according to the middle-order traversal and post-order traversal of a tree.
Note: You can assume that there are no duplicated elements in the tree.
💡 ideas:
Let’s first look at a tree, what does middle-order traversal and post-order traversal look like
According to the characteristics of middle-order traversal and post-order traversal, it can be concluded that:
- In a post-traversal sequence, the last element is the root node of the tree
- In a middle-order traversal sequence, the left of the root node is the left subtree, and the right of the root node is the right subtree
So how do we restore the binary tree?
You can take the last node of the post-ordered sequence to slice the middle-ordered sequence, and then slice the post-ordered sequence according to the middle-ordered sequence, and then slice the post-ordered sequence in reverse, layer by layer, so that the last element of each post-ordered sequence is the element of the node.
Let’s take a look at the process:
So what are the steps?
- If the array length is 0, the node is empty.
- If not empty, the last element of the post-ordinal group is taken as the node element
- Find the position of the last element in the middle ordinal group as the cut point
- Cut the middle ordinal group into the middle order left array (left subtree) and the middle order right array (right subtree)
- Cut ordinal group, cut into post-order left array and post-order right array
- Recurse left and right intervals
Here’s another problem, we need to determine where the next round starts and ends.
We take [inStart, inEnd], [postStart, postEnd], and rootIndex to mark the root node.
- Left subtree – Middle ordinal group
inStart = inStart.inEnd = rootIndex - 1 - Left subtree – rear ordinal group
postSrart = postStart.postEnd = postStart + ri - is - 1(PE calculation process explained, the sequential array starting position plus the left subtree length -1 is the end of the sequence, the length of the left subtree = root node index – left subtree) - Right subtree – Middle ordinal group
inStart = roootIndex + 1, inEnd = inEnd - Right subtree – rear ordinal group
postStart = postStart + rootIndex - inStart, postEnd - 1
The code is as follows:
/** * 106. Construct a binary tree * by traversing sequences in middle and rear order https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ *@param inorder
* @param postorder
* @return* /
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
/ * * *@paramInorder ordinal group *@paramInStart ordinal group starting point *@paramInEnd Indicates the ordinal group end *@paramPostorder post-ordinal group *@paramPostStart Indicates the start of the ordinal group *@paramPostEnd end of the ordinal group *@return* /
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
// No element
if (inEnd - inStart < 1) {
return null;
}
// There is only one element
if (inEnd - inStart == 1) {
return new TreeNode(inorder[inStart]);
}
// The last element of the ordinal group is the root node
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
// Find the position of the value in the middle ordinal group inorder according to the root node
for (int i = inStart; i < inEnd; i++) {
if(inorder[i] == rootVal) { rootIndex = i; }}// Cut the left and right subtrees according to rootIndex
root.left = buildTree(inorder, inStart, rootIndex,
postorder, postStart, postStart + (rootIndex - inStart));
root.right = buildTree(inorder, rootIndex + 1, inEnd,
postorder, postStart + (rootIndex - inStart), postEnd - 1);
return root;
}
Copy the code- 🚗 Time complexity O(n).
LeetCode105. Constructing binary trees by traversing sequences of preorder and middle order
☕ Title: 105. Constructing binary trees from pre-ordered and middle-ordered traversal sequences (leetcode-cn.com/problems/co…)
❓ Difficulty: medium
📕 description:
Preorder and inorder of a tree are given. Construct a binary tree and return its root node.
💡 ideas:
Similar to the previous problem, the first node of the sequential traversal is the root node, take the first element of the sequential traversal group to cut the middle ordinal group, and then take the middle ordinal group to cut the ordinal group.
The code is as follows:
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length-1,
inorder, 0, inorder.length-1);
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
// Recursive termination condition
if (inStart > inEnd || preStart > preEnd) return null;
// The root value
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// The root node subscript
int rootIndex = inStart;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break; }}// Find the left and right subtrees recursively
root.left=buildTree(preorder, preStart + 1, preStart + (rootIndex - inStart),
inorder, inStart, rootIndex - 1);
root.right=buildTree(preorder, preStart + (rootIndex - inStart) + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
Copy the code🚗 Time complexity: O(n)
LeetCode654. Maximum binary tree
☕ Title: 654. Most binary trees (leetcode-cn.com/problems/ma…)
❓ Difficulty: medium
📕 description:
Given an integer array nums with no repeating elements. A maximum binary tree built directly recursively from this array is defined as follows:
- The root of a binary tree is the largest element in the array NUMs.
- The left subtree is the maximum binary tree recursively constructed from the left of the maximum in the array.
- The right subtree is the largest binary tree recursively constructed from the right portion of the maximum value in the array.
Returns the maximum binary tree built with the given array NUMs.
Example 1:
Output: input: nums =,2,1,6,0,5 [3] [6,3,5, null, 2, 0, null, null, 1] : recursive calls as shown below: The maximum value in - [3,2,1,6,0,5] is 6, the left part is [3,2,1], and the right part is [0,5]. The maximum value in - [3,2,1] is 3, the left part is [], and the right part is [2,1]. - An empty array with no child nodes. The maximum value in - [2,1] is 2, the left part is [], and the right part is [1]. - An empty array with no child nodes. - There is only one element, so the child node is a node with the value 1. The maximum value in - [0,5] is 5, the left part is [0], and the right part is []. - There is only one element, so the child node is a node with the value 0. - An empty array with no child nodes.Copy the codeExample 2:
Nums = [3,2,1] output: [3, NULL,2, NULL,1]Copy the code💡 ideas:
The maximum nums element is the root node, and then recurse to the left and right parts of the maximum element.
The code is as follows:
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
// No element
if (end - start < 1) {
return null;
}
// Only one element left
if (end - start == 1) {
return new TreeNode(nums[start]);
}
// Maximum position
int maxIndex = start;
/ / Max
int maxVal = nums[start];
for (int i = start + 1; i < end; i++) {
if(nums[i] > maxVal) { maxVal = nums[i]; maxIndex = i; }}/ / the root node
TreeNode root = new TreeNode(maxVal);
// The left half of the recursion
root.left = constructMaximumBinaryTree(nums, start, maxIndex);
// Recurse the right half
root.right = constructMaximumBinaryTree(nums, maxIndex + 1, end);
return root;
}
Copy the code- 🚗 time complexity: find the maximum array time complexity O(n), recursive time complexity O(n), so the total time complexity O(n²).
LeetCode617. Merge binary trees
☕ Title: 617. Merging binary trees (leetcode-cn.com/problems/me…)
❓ Difficulty: Simple
📕 description:
Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.
You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary tree.
Example 1:
Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: merged Tree: 3 / \ 4 5 / \ 5 4 7Copy the codeNote: The merge must start at the root of both trees.
💡 ideas:
Let’s do a simple problem for confidence.
So what’s going on here?
It traverses the roots, left, and right in advance.
We’re not saying we can’t change the tree structure, but we’re going to merge the two trees with a new tree.
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// Recursive end condition, one node is empty
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
/ / the new tree
TreeNode root = new TreeNode(0);
/ / merge
root.val = root1.val + root2.val;
/ / the left subtree
root.left = mergeTrees(root1.left, root2.left);
/ / right subtree
root.right = mergeTrees(root1.right, root2.right);
return root;
}
Copy the code- 🚗 Time complexity: O(n).
Find the properties of the binary search tree
Binary search trees we’ve seen before, small on the left and big on the right, so let’s start looking at binary search trees.
LeetCode700. Search in binary search tree
☕ Title: 700. Search in binary search trees (leetcode-cn.com/problems/se…)
❓ Difficulty: Simple
📕 description:
Given the root node of a binary search tree (BST) and a value. You need to find nodes in BST that have a value equal to the given value. Returns the subtree rooted with this node. If the node does not exist, NULL is returned.
For example,
Given a binary search tree: 4 / \ 2 7 / \ 1 3 and the values: 2Copy the codeYou should return such as subtree:
2
/ \
1 3
Copy the codeIn the example above, if the value we are looking for is 5, but there are no nodes with a value of 5, we should return NULL.
💡 ideas:
This also has no what to say, front order traversal line.
But when we recurse to left and right subtrees, we can take advantage of the fact that the left is smaller and the right is larger.
📜 code is as follows:
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
// recursive left subtree
if (val < root.val) {
return searchBST(root.left, val);
}
// Recursive right subtree
if (val > root.val) {
return searchBST(root.right, val);
}
return null;
}
Copy the code- 🚗 Time complexity: O(logn).
LeetCode98. Validate binary search trees
☕ Title: 98. Validate binary search trees (leetcode-cn.com/problems/va…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, determine whether it is a valid binary search tree.
Suppose a binary search tree has the following characteristics:
- The left subtree of a node contains only numbers less than the current node.
- The right subtree of a node only contains numbers greater than the current node.
- All left and right subtrees must themselves also be binary search trees.
Example 1:
Input: 2 / \ 1 3 Output: trueCopy the codeExample 2:
Input: 5 / \ 1 4 / \ 3 6 Output: false Description: Input: [5,1,4, NULL, NULL,3,6] The root node has a value of 5, but its right child node has a value of 4.Copy the code💡 ideas:
We know that middle order traversal binary search tree, output is ordered sequence, so upper middle order traversal.
When comparing root, we can compare root to the previous root.
📜 code is as follows:
class Solution {
private TreeNode pre;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
/ / the left subtree
boolean isValidLeft = isValidBST(root.left);
if(! isValidLeft){return false;
}
/ / root
if(pre! =null&&pre.val>=root.val){
return false;
}
pre=root;
/ / right subtree
boolean isValidRight = isValidBST(root.right);
returnisValidRight; }}Copy the code- 🚗 Time complexity O(n)
LeetCode530. Minimum absolute difference of binary search trees
☕ Title: 98. Validate binary search trees (leetcode-cn.com/problems/va…)
❓ Difficulty: Simple
📕 description:
You are given a binary search tree in which all nodes are non-negative. Compute the minimum absolute value of the difference between any two nodes in the tree.
Example:
Input: 1\3/2 Output: 1 Explanation: The minimum absolute difference is 1, where the absolute value of the difference between 2 and 1 is 1 (or 2 and 3).Copy the code💡 ideas:
The middle order traversal of a binary search tree is ordered.
That’s the same as the last problem, middle order traversal. We also record the last node traversed, and then take the maximum value of the difference with the current node.
📜 code is as follows:
class Solution {
TreeNode pre;
Integer res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
/ / left
getMinimumDifference(root.left);
/ /
if(pre ! =null) {
res = Math.min(res, root.val-pre.val);
}
pre=root;
/ / rightgetMinimumDifference(root.right); }}Copy the code- 🚗 Time complexity O(n)
LeetCode501. Modes in binary search trees
☕ Title: 501. Modes in binary search trees (leetcode-cn.com/problems/fi…)
❓ Difficulty: Simple
📕 description:
Given a binary search tree (BST) with the same value, find all the modes (the element with the highest frequency) in the BST.
Assume that BST has the following definition:
- The value of the node contained in the node left subtree is less than or equal to the value of the current node
- The value of the node in the right subtree of the node is greater than or equal to the value of the current node
- Both the left and right subtrees are binary search trees
Example: given BST [1,null,2,2],
1 times 2 over 2Copy the codeReturn to the [2].
Tip: If the mode number is more than 1, the output order is not considered
** Advanced: ** Can you not use the extra space? Assume that the overhead of the implicit call stack generated by recursion is not taken into account
💡 ideas:
If it’s a binary tree, the best thing we can think of is to introduce a map to count the set of high frequency elements.
But binary search trees, we then use its middle order to traverse the ordered property.
Prev represents the previous node, count represents the number of current values, maxCount represents the maximum number of repeated digits, and a list is used to store the results.
-
If the node value is equal to prev, count is incremented by one,
-
If the object is not equal to prev, the next new value is encountered, update prev to the new value, and set count=1;
- If count==maxCount, the value of the current node is added to the collection list.
- If count>maxCount, the list is cleared first, then the current node value is added to the list, and finally the maxCount value is updated.
📜 code is as follows:
class Solution {
// Record the current number
int count = 0;
// Maximum number
int maxCount = 1;
/ / precursor
TreeNode pre=new TreeNode(0);
// Store the mode list
List<Integer> res = new ArrayList<>();
public int[] findMode(TreeNode root) {
dfs(root);
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
public void dfs(TreeNode root) {
if (root == null) return;
/ / left
dfs(root.left);
/ /
if (root.val == pre.val) {
// if the same as the previous one, count++
count++;
} else {
/ / otherwise
/ / the pre in the future
pre = root;
// Refresh count to 1
count = 1;
}
// If it is the most frequent value
if (count == maxCount) {
res.add(root.val);
} else if (count > maxCount) {
// If the maximum number of occurrences is exceeded
// Empty the result combination
res.clear();
// Add a new Max element
res.add(root.val);
// Refresh the Max count
maxCount = count;
}
/ / rightdfs(root.right); }}Copy the code- 🚗 Time complexity: O(n)
- 🏠 Space complexity: O(n)
Common ancestor problem of binary tree
LeetCode236. The most recent common ancestor of binary trees
☕ Title: 501. Modes in binary search trees (leetcode-cn.com/problems/fi…)
❓ Difficulty: Simple
📕 description:
Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.
The definition of the nearest common ancestor in Baidu Encyclopedia is as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).
Example 1:
Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.Copy the codeExample 2:
Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the nearest common ancestor node can be the node itself.Copy the code💡 ideas:
We thought, look for the common ancestor, if only we could go back from the two nodes.
What can we do about it?
Remember when we did the path problem earlier? We used a method called backtracking.
Let’s see what the order is. Left, right, root, this is not the order traversal!
So how do you tell if a node is the common ancestor of q and P? What are the scenarios?
- Q and Q are both subtrees of this node, and the opposite side (P left, Q right or P right, Q left)
- Q is in the subtree of P
- Q is in the subtree of P
How do I write this backward recursion?
Let’s look at the three elements of recursion [8] :
- Input parameter and return value
We need a recursive function that returns the value of the node to tell us whether we found the node q or p.
- Termination conditions
Returns if node P or q is found, or if an empty node is encountered.
- Single layer recursive logic
We need to determine if we found p and Q.
-
If leftLeftLeft and rightrightright are both null, the root subtree does not contain P or Q, and null is returned.
-
If left and right are not empty at the same time, p and Q are on the opposite side of root (on the left and right subtrees respectively), so root is the nearest common ancestor
-
When leftLeftLeft is empty, right is not empty: p and q are not in the left subtree of root, return right directly. It can be divided into two cases:
-
P,q one of them is in the right subtree of root, and right points to P.
-
Both nodes p and Q are in the right subtree of root, and the right at this time points to the nearest common ancestor node
-
-
When left is not empty, right is empty: same as case 3.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Recursive end condition
if (root == null || root == p || root == q) return root;
/ / left
TreeNode left = lowestCommonAncestor(root.left, p, q);
/ / right
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Four cases of judgment
// Both left and right are empty
if (left == null && right == null) {
return null;
}
// Both left and right are not empty
if(left ! =null&& right ! =null) {
return root;
}
//left is null, right is not null
if (left == null&& right ! =null) {
return right;
}
//left is not empty, right is empty
if(left ! =null && right == null) {
return left;
}
return null;
}
Copy the codeSimplify the code:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Recursive end condition
if (root == null || root == p || root == q) return root;
/ / left
TreeNode left = lowestCommonAncestor(root.left, p, q);
/ / right
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left ! =null&& right ! =null) return root;
if (left == null) return right;
return left;
}
Copy the code- 🚗 Time complexity: O(n).
LeetCode235. The most recent common ancestor of binary search trees
☕ Title: 501. Modes in binary search trees (leetcode-cn.com/problems/fi…)
❓ Difficulty: Simple
📕 description:
Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.
The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).
For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)
Example 1:
Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the codeExample 2:
Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the codeDescription:
- All nodes have unique values.
- P and Q are different nodes and exist in the given binary search tree.
💡 ideas:
And then we look at the nearest common ancestor of a binary search tree, and we can just use the nearest common ancestor of a binary tree to do it again.
But is it possible to exploit the properties of our binary search tree?
B: Sure.
The nodes of our binary tree are small on the left and large on the right. As long as the current node is between [p,q], it can be determined that the current node is the nearest common ancestor.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
/ / left
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
/ / right
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
Copy the code- 🚗 Time complexity: O(n)
The modification and construction of binary search tree
LeetCode701. Insert operations in binary search trees
☕ Title: 701. Insert operations in binary search trees (leetcode-cn.com/problems/in…)
❓ Difficulty: medium
📕 description:
Inserts the value into the binary search tree (BST) given the root node and the value in the tree to be inserted. Returns the root node of the inserted binary search tree. The input data guarantees that the new value is different from any node in the original binary search tree.
Note that there may be several effective ways to insert, as long as the tree remains a binary search tree after insertion. You can return any valid result.
Example 1:
Input: root = [4,2,7,1,3], val = 5 output: [4,2,7,1,3,5]Copy the code
💡 ideas:
Note: there is no limit to how you can insert this problem.
As in the sample, two cases are given:
- The first way is to take someone else’s place, and you can see that the 5 and 4 positions have been adjusted so that the tree meets the requirements of a balanced binary tree, but this is definitely a hassle to implement
- The second option: we can be lazy and find a space. We can search for a leaf node that fits the size relationship and insert it into the subtree of the leaf node.
The code is as follows:
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
/ / left
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
}
/ / right
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}
Copy the code- 🚗 Time complexity: O(n).
LeetCode450. Delete nodes in binary search tree
☕ Title: 701. Insert operations in binary search trees (leetcode-cn.com/problems/in…)
❓ Difficulty: medium
📕 description:
Given the root node of a binary search tree root and a value of key, delete the nodes corresponding to key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated).
In general, node deletion can be divided into two steps:
- First find the node to delete;
- If found, delete it.
Note: The algorithm time complexity is O(h), h is the height of the tree.
Example:
Root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ 2 4 7 5 / \ 3 6 / \ 2 4 7 A correct answer is [5,4,6,2,null,null,7], as shown below. 5 / \ 4 6 / \ 27 Another correct answer is [5,2,6,null,4,null,7]. 5 / \ 2 6\4 7Copy the code💡 ideas:
Oh, we got lazy on the last one, but we can’t get lazy on this one.
If we delete a node, we’re digging a hole, and we have to figure out how to fill it, and we have to make the binary tree fit the definition of a balanced binary tree.
Finding the delete node, let’s list all the cases:
- Left and right children are empty (leaf node), delete node directly
- If the node is deleted, the left child is empty and the right child is not empty. If the node is deleted, the right child fills the bit
- If the node is deleted, the right child is empty and the left child is not empty. If the node is deleted, the left child fills the space
Deleted nodeIf neither the left child node nor the left child node is empty, place the left child of the left subtree of the deleted node on the left child of the leftmost node of the right subtree of the deleted node. That’s a tricky one, isn’t it? Let’s talk about it.
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
// Find the deleted node
if (root.val == key) {
//1. Left and right children are empty (leaf node)
if (root.left == null && root.right == null) return null;
//2. The left child is empty and the right child is not empty
if (root.left == null) return root.right;
//3. The right child is empty, the left child is not empty
if (root.right == null) return root.left;
//4. Neither the left nor the right child is empty
if(root.left ! =null&& root.right ! =null) {
// Find the leftmost node of the right subtree
TreeNode node = root.right;
while(node.left ! =null) {
node = node.left;
}
// Place the left subtree of the node to be deleted in the left subtree of the node
node.left = root.left;
// Save the root node for deletion
TreeNode temp = root;
//root right child as the new root node
root = root.right;
returnroot; }}/ / the left child
if (key < root.val) root.left = deleteNode(root.left, key);
/ / right child
if (key > root.val) root.right = deleteNode(root.right, key);
return root;
}
Copy the codeCode points are bloated, but each case is clear and I’m too lazy to simplify.
- 🚗 Time complexity: O(n).
LeetCode669. Prune binary search trees
☕ Title: 701. Insert operations in binary search trees (leetcode-cn.com/problems/in…)
❓ Difficulty: medium
📕 description:
You are given the root node of the binary search tree, root, with a minimum boundary low and a maximum boundary high. By pruning the binary search tree, the values of all nodes are in [low, high]. Pruning the tree should not change the relative structure of the elements that remain in the tree (that is, if they are not removed, the original parent and child relationships should remain). It can be argued that there is a single answer.
So the result should return the new root node of the pruned binary search tree. Note that the root node may change depending on the given boundary.
Example 1:
Root = [1,0,2], low = 1, high = 2Copy the codeExample 2:
Input: root = [3,0,4, NULL,2, NULL, NULL,1], low = 1, high = 3Copy the code💡 ideas:
Schematic diagram of pruning:
What is the general process?
Traversing the binary tree:
- If the current node is in [low, high], continue traversing
- If the current node is lower than low, it is the node to be pruned. Search its right subtree to find the node in the range of [low, high]
- If the current node is greater than high and is the node to be pruned, search its left subtree to find the node in the range [low, high]
The code is as follows:
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
Copy the code- 🚗 Time complexity: O(n).
LeetCode538. Convert binary search tree to cumulative tree
☕ Title: 701. Insert operations in binary search trees (leetcode-cn.com/problems/in…)
❓ Difficulty: medium
📕 description:
Convert the root node of the binary search Tree to the Greater Sum Tree. Make the new value of node of each node equal to the Sum of the values Greater than or equal to node.val in the original Tree.
As a reminder, binary search trees satisfy the following constraints:
- The left subtree of a node contains only nodes whose keys are smaller than the node’s keys.
- The right subtree of a node contains only nodes whose keys are greater than the node’s keys.
- The left and right subtrees must also be binary search trees.
💡 ideas:
What about this one?
If I had an array [3,5,6], we could immediately say, let’s go back to front.
But this is a binary search tree, and we know that the middle order of a binary search tree is an ordered sequence, so let’s just reverse the middle order.
Middle order is left, right, middle, let’s change it to right, middle, left.
class Solution {
int preVal = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
public void dfs(TreeNode root) {
if (root == null) return;
// Reverse middle order, right left middle orderdfs(root.right); root.val += preVal; preVal = root.val; dfs(root.left); }}Copy the code- 🚗 Time complexity: O(n).
conclusion
Here’s the catchphrase:
Do simple things repeatedly, do repetitive things seriously, do serious things creatively!
I am three points evil, a full stack of literary and military development.
Like, pay attention not to get lost, see you next time!
The blogger is an algorithm adorable new, brush topic ideas and routes mainly referred to the following big guy! Suggest attention!
Reference:
[1]. Github.com/youngyangya…
[2]. labuladong.gitbook.io/algo/
[3]. leetcode-cn.com/u/sdwwld/
[4]. Leetcode-cn.com/problems/bi…
[5]. Leetcode-cn.com/problems/bi…
[6]. Leetcode-cn.com/problems/bi…
[7]. Leetcode-cn.com/problems/co…
[8]. Leetcode-cn.com/problems/lo…
[9]. Leetcode-cn.com/problems/de…