Tree¶
First up and down the outline of this article, this is a brain map I drew with mindmap, and then I will continue to improve, and gradually improve other topics.
You can also use vscode blink-mind to open the source file for viewing. There are some notes in it that you can click to open and view. The source files can be obtained by replying to the mind map on my public account "Like Plus", and the mind map will continue to update more content in the future. vscode plug-in address: https://marketplace.visualstudio.com/items?itemName=awehook.vscode-blink-mind
This series includes the following topics:
-Almost finished reading all the linked list questions, I found these things. . . -Almost finished all the tree questions of Likou, I found these things. . . (This is this article)
A little bit of talk¶
First, let’s light up the protagonist of this article-the tree (my makeup skills are okay_):
Tree Tag There are a total of 175 questions in leetcode. In order to prepare for this topic, I spent a few days reviewing almost all tree topics in LeetCode.
Except for 35 locked questions, 1 unworkable question (I don't know why I can't do 1628 question), and 4 questions with tree labels but graphs. I did all the others. By focusing on these questions, I found some interesting information, which I will share with you today.
Edible Guide¶
Hi everyone, my name is lucifer. Today I bring you the topic "Tree". In addition, in order to maintain the focus and practicality of the chapter, some content is omitted, such as Huffman trees, prefix trees, balanced binary trees (red-black trees, etc.), and binary heaps. These contents are relatively not so practical. If you are also interested in these contents, you can pay attention to my warehouse leetcode algorithm problem solution, If you have something you want to see, you can leave a message and let me know~
In addition, I should inform you in advance that a lot of the content in this article relies on recursion. Regarding the exercise of recursion, I recommend that you draw the recursive process on paper and substitute it several times manually. After the brain is familiar with recursion, there is no need to work so hard. Students who are too lazy to draw can also find a website that visualizes recursion, such as https://recursion.now.sh/. After you have a certain understanding of recursion, carefully study the various tree traversal methods, then read this article, and finally do a job at the end of the article, so that there is no big problem with recursion.
Later in the article, in the "Two Basic Points-Depth First Traversal" section, I also proposed a method for how to practice the recursive thinking of tree traversal
Finally, it should be emphasized that this article is only a common routine to help you get the tree topic, but it does not mean that all the test points involved in the tree topic are covered. For example, tree DP is not in the scope of this article, because this kind of question focuses more on DP. If you don’t understand DP, you will probably not be able to do it. What you need is to learn tree and DP before learning tree DP . If you are interested in these contents, you can look forward to my follow-up topic.
Foreword¶
When it comes to trees, what everyone is more familiar with is the tree in reality, and the tree in reality looks like this:
The tree in the computer is actually the reflection of the tree in reality.
The data structure of a computer is an abstraction of the relationship between objects in the real world. For example, the genealogy of the family, the organization of personnel in the company structure, the folder structure in the computer, the dom structure of html rendering, etc. These hierarchical structures are called trees in the computer field.
First of all, make it clear that a tree is actually a logical structure. For example, when the author usually writes about complex recursion, even though the topic I am doing is not a tree, I will draw a recursion tree to help me understand it.
Tree is an important thinking tool
Take the simplest calculation of fibonacci sequence as an example:
Obviously, its input parameters and return value are not trees, but it does not affect our thinking with trees.
Continuing back to the above code, based on the above code, the following recursive tree can be drawn.
The edge of the tree represents the return value, and the tree node represents the value that needs to be calculated, that is, fn(n).
Taking the calculation of fibbonacci of 5 as an example, the process is roughly like this (an animation):
This is actually a post-order traversal of a tree, do you think the tree (logical tree) is very important? We will talk about post-order traversal later, and now everyone knows that this is the case.
You can also go to this website to view the single-step execution effect of the above algorithm. Of course, there are more animated demonstrations of algorithms on this website.
The arrow direction in the above figure is to facilitate everyone's understanding. In fact, the real tree structure is when the arrow direction turns downward.
The generalized tree is really useful, but its scope is too large. The topic of the tree in this article is a narrow tree, which refers to the topic of the tree structure of the input (parameter) or output (return value).
basic concepts¶
The basic concept of the tree is not difficult, in order to save space, I will briefly briefly. For the points you are not familiar with, please look up relevant information yourself. I believe that everyone is not looking at these, you should want to see some different things, such as some routines for doing questions.
The tree is a non-linear data structure. The basic unit of the tree structure is the node. The links between nodes are called branches. Nodes and branches form a tree, and the beginning of the structure is called the root, or root node. Nodes other than the root node are called child nodes. Nodes that are not linked to other child nodes are called leaf nodes. The following figure is a typical tree structure:
Each node can be represented by the following data structure:
Other important concepts:
-Tree height: The maximum value from node to leaf node is its height. -Depth of the tree: height and depth are opposite, height is counted from bottom to top, and depth is counted from top to bottom. Therefore, the depth of the root node and the height of the leaf nodes are 0. -The level of the tree: the root is defined at the beginning, the root is the first level, and the children of the root are the second level. -Binary tree, trinomial tree,. . . The N-ary tree can be determined by the number of its child nodes at most, and at most N is an N-ary tree.
Binary Tree¶
Binary tree is a kind of tree structure. Two forks means that each node at most has only two child nodes. We are accustomed to call it the left node and the right node.
Note that this is just the name, not the left and right sides of the actual location
Binary tree is also the most common tree we do algorithmic problems, so we spend a lot of time to introduce it, and everyone will also spend a lot of time focusing on mastering it.
The binary tree can be represented by the following data structure:
Node {
value: any; // The value of the current node
left: Node | null; // left son
right: Node | null; // right son
}
Binary tree classification¶
-Complete binary tree -Full binary tree -Binary search tree -Balanced Binary Tree -Red-Black Tree -. . .
Representation of Binary Tree¶
-Linked list storage -Array storage. Very suitable for complete binary trees
How difficult is the tree question?¶
Many people find trees to be a difficult topic. In fact, as long as you have the know-how, it is not that difficult.
Judging from the official difficulty label, there are a total of 14 tree titles in difficult difficulty. Among them, there is 1 label labeled tree but it is a picture title, so the difficulty rate is 13/175, which is 7.4%. about. If the 5 locked channels are excluded, only 9 channels are difficult. I believe you can make most difficult questions after reading the contents of this section.
From the perspective of the pass rate, only less than one-third have an average pass rate of less than 50%, and other (most of the questions) have a pass rate of more than 50%. What is the concept of 50%? This is actually very high. For example, the average pass rate of BFS is almost 50%. However, the average pass rate of the difficult dichotomy and dynamic programming is almost 40%.
Don’t put pressure on trees. Trees and linked lists are relatively easy topics. Today, Lucifer brings you a formula*_ one center, two basic points, three question types, four important concepts, and seven skills_ *, to help you overcome the difficulty of the tree.
One Center¶
A center refers to tree traversal. The topic of the entire tree has only one central point, and that is the traversal of the tree. You must keep it in mind.
No matter what the topic is, the core is the traversal of the tree. This is the basis of everything. If the traversal of the tree is not discussed later, it is useless.
In fact, the essence of tree traversal is to visit every element in the tree (isn’t it true for any data structure traversal?). But how to access it? I can't directly access the leaf nodes. I have to start from the root node and then access the child nodes based on the child node pointers. However, the child nodes have multiple directions (two binary trees at most), so there is the question of which one to visit first. This results in different traversal methods.
The access order of the left and right child nodes is usually not important, and there are some subtle differences in rare cases. For example, if we want to visit the bottom left node of a tree, the order will have an impact, but there will be fewer such problems.
The traversal is not the purpose. The traversal is for better processing. The processing here includes searching, modifying the tree, and so on. Although the tree can only be accessed from the root, we can choose to do the processing when the visit is completed, or to do the processing before the visit is returned. The two different methods are post-order traversal and* *First-order traversal**.
Regarding the specific traversal, I will tell you in detail later, as long as you know how these traversals come from.
The tree traversal can be divided into two basic types, namely depth-first traversal and breadth-first traversal. These two traversal methods are not unique to the tree, but they accompany all the problems of the tree. It is worth noting that these two traversal methods are just a logic, so the theory can be applied to any data structure, such as 365. Kettle Problem, you can use breadth-first traversal for the state of the kettle, and the state of the kettle can be represented by a two-tuple.
Unfortunately, the breadth-first traversal solution of this question will time out when submitted on LeetCode
Tree traversal and iteration¶
Many children said that the recursive writing of the front, middle and back of the binary tree is okay, but the iteration cannot be written, and they asked me if there is any good way.
Here is a practical technique for writing an iterative traversal tree, unifying the three tree traversal methods, you can't go wrong, this method is called two-color notation. If you know this technique, you can practice only recursion. Then in the interview, if it is really required to use iteration or the kind of questions that have special requirements for performance, then you can use my method. Let me talk about this method in detail.
We know that among the garbage collection algorithms, there is an algorithm called three-color notation. which is:
-Use white to indicate not yet visited -Gray means that the child node has not been fully accessed -Black means all child nodes are visited
Then we can imitate its idea and use two-color notation to unify the three traversals.
The core ideas are as follows:
-Use colors to mark the status of nodes, new nodes are white, and visited nodes are gray. -If the node encountered is white, mark it as gray, and then put its right child node, self, and left child node onto the stack in turn. -If the encountered node is gray, the value of the node is output.
The in-order traversal achieved using this method is as follows:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
It can be seen that the realization of WHITE means the first entry process in the recursion, and Gray means the process of returning from the leaf node in the recursion. Therefore, this iterative way of writing is closer to the essence of recursive writing.
If you want to implement the pre-order and post-order traversal, you only need to adjust the stacking order of the left and right child nodes, and there is no need to make any changes in the other parts.
(The first, middle, and last traversal only needs to adjust the position of these three sentences)
It can be seen that the three-color notation is similar to the recursive form, so it is easy to remember and write.
Some students may say that every node here will be pushed and popped twice. Compared with the normal iterative push and pop times, the number of times is doubled. Is this performance acceptable? What I want to say is that this increase in time and space is only an increase in the constant term, and in most cases, the program will not cause too much impact. Except that sometimes the game will be more disgusting, it will be very often ** (card often refers to the optimization of the code running speed through the method related to the computer principle and not related to the theoretical complexity). Looking at it conversely, most of the code you write is recursive. You must know that due to the overhead of the memory stack, the performance of recursion is usually worse than the two-color notation here. So why not use a stack iteration? More extreme, why doesn't everyone use morris to traverse?
Morris traversal is an algorithm that can complete tree traversal in a constant space complexity.
I think that in most cases, people don't need to pay much attention to such small differences. In addition, if this traversal method is completely mastered, it is not difficult to write an iteration into the stack based on the recursive idea. It's nothing more than stacking when calling a function, and popping out when a function returns. For more content about binary tree traversal, you can also visit the topic I wrote before "Binary Tree Traversal".
Summary¶
To summarize briefly, one center of the topic of the tree is the traversal of the tree. There are two types of tree traversal, depth-first traversal and breadth-first traversal. Regarding the different depth-first traversal of the tree (pre-order, middle-order and post-order traversal), the iterative writing method is easy for most people to make mistakes, so I introduced a unified three traversal method-two-color notation, so You don’t have to worry about writing the first, middle, and last traversal of the iterated tree in the future. If you are thoroughly familiar with this writing method, you can memorize and practice a stacking or even Morris traversal.
It is also very simple to implement recursion using one-time stacking and popping iterations. It is nothing more than recursive thinking, but you put the recursive body inside the loop. You can look back after getting familiar with recursion and it will be easier to understand. The recursive technique of deep traversal of the tree will be explained in the "Two Basic Points" section later.
Two basic points¶
As mentioned above, there are two basic methods of tree traversal, namely, depth-first traversal (hereinafter referred to as DFS) and breadth-first traversal (hereinafter referred to as BFS). These are the two basic points**. These two traversal methods will be subdivided into several methods below. For example, **DFS is subdivided into front-middle-post-order traversal, and BFS is subdivided into layers with and without layers**.
**DFS is suitable for some violent enumeration problems. If DFS uses the function call stack, it can be easily implemented using recursion. **
BFS is not hierarchical traversal¶
While BFS is suitable for finding the shortest distance, this is different from level traversal, and many people confuse it. Here to emphasize that level traversal and BFS are completely different things.
Hierarchical traversal is to traverse the tree layer by layer, and visit the tree in the order of hierarchy.
(Hierarchy traversal icon)
The core of BFS is that it can be terminated early when seeking the shortest problem. This is its core value. Hierarchical traversal is a by-product of BFS that does not require early termination. This early termination is different from the early termination of DFS's pruning, but the early termination of finding the nearest target. For example, if I want to find the closest target node, BFS can return directly when it finds the target node. And DFS must exhaust all possible to find the nearest, this is the core value of BFS. In fact, we can also use DFS to achieve the effect of level traversal. With the help of recursion, the code will be even simpler.
If you find any node that meets the conditions, it doesn't have to be the nearest, then DFS and BFS are not much different. At the same time, for the sake of writing simplicity, I usually choose DFS.
The above is a brief introduction of the two traversal methods. Below we will give a detailed explanation of the two.
Depth first traversal¶
The depth-first search algorithm (English: Depth-First-Search, DFS) is an algorithm for traversing trees or graphs. Traverse the nodes of the tree along the depth of the tree and search the branches of the tree as deep as possible. When the edges of node v have been explored, the search will backtrack to the starting node of the edge where node v is found. This process continues until all nodes reachable from the source node have been found. If there are still undiscovered nodes, select one of them as the source node and repeat the above process. The whole process is repeated until all nodes are visited, which is a blind search.
Depth-first search is a classic algorithm in graph theory. The depth-first search algorithm can generate the corresponding topological sorting table of the target graph, and the topological sorting table can conveniently solve many related graph theory problems, such as the maximum path problem. For inventing the "depth-first search algorithm", John Hopcroft and Robert Tayan jointly won the highest award in the computer field in 1986: the Turing Award.
As of now (2020-02-21), there are 129 questions in LeetCode for depth-first traversal. The question types in LeetCode are definitely super big. As for the tree problem, we can basically use DFS to solve it, and even we can do hierarchical traversal based on DFS, and since DFS can be done based on recursion, the algorithm will be more concise. In situations where performance is very demanding, I suggest you use iteration. Otherwise, try to use recursion. Not only is it simple and fast to write, but it is also not easy to make mistakes.
DFS diagram:
(Image from https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search)
Algorithm flow¶
- First put the root node into stack.
- Take the first node from stack and check if it is the target. If all nodes are found, the search ends and the results are returned. Otherwise, add one of its direct child nodes that have not been tested to stack.
- Repeat step 2.
- If there is no direct child node that has not been detected. Add the upper level node to stack. Repeat step 2.
- Repeat step 4.
- If stack is empty, it means that the whole picture has been checked-that is, there is no target to be searched in the picture. End the search and return "target not found".
**The stack here can be understood as a stack implemented by yourself, or as a call stack. If it is a call stack, it is recursion, if it is a stack implemented by itself, it is iteration. **
Algorithm template¶
A typical general DFS template might look like this:
const visited = {}
function dfs(i) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
visited[i] = true // mark the current state as searched
for (according to the next state j that i can reach) {
if (!visited[j]) {// If state j has not been searched
dfs(j)
}
}
}
The above visited is to prevent the endless loop caused by the existence of the ring. And we know that the tree does not have a ring, so most of the topics of the tree do not need to be visited, unless you modify the structure of the tree, for example, the left pointer of the left subtree points to itself, and there will be a ring at this time. Another example is 138. Copy linked list with random pointer This question needs to record the nodes that have been copied, and these need to be recorded visited The problem of the tree of information is very rare**.
Therefore, the DFS of a tree is more:
function dfs(root) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
for (const child of root.children) {
dfs(child)
}
}
Almost all topics are binary trees, so the following template is more common.
function dfs(root) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
dfs(root.left)
dfs(root.right)
}
For our different topics, in addition to if (except for the different parts that meet specific conditions), we will also write some unique logics. These logics are written in different positions and have completely different effects. So what is the impact of different positions, when and where should they be written? Next, we will talk about two common DFS methods.
Two common categories¶
Preorder traversal and postorder traversal are the two most common DFS methods. The other traversal method (in-order traversal) is generally used to balance the binary tree, and we will talk about this later in the Four Important Concepts part.
Preorder traversal¶
If your code is written like this (note the location of the main logic):
function dfs(root) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
// main logic
dfs(root.left)
dfs(root.right)
}
Then we call it preorder traversal at this time.
Follow-up traversal¶
And if your code is written like this (note the location of the main logic):
function dfs(root) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
dfs(root.left)
dfs(root.right)
// main logic
}
Then we call it post-order traversal at this time.
It is worth noting that we sometimes write code like this:
function dfs(root) {
if (satisfy certain conditions) {
// Return the result or exit the search space
}
// do something
dfs(root.left)
dfs(root.right)
// do something else
}
As in the above code, we executed some codes when entering and exiting the left and right subtrees. So at this time, is it pre-order traversal or subsequent traversal? In fact, this is a mixed traversal. But here we only consider the location of main logic, the key word is main logic.
If the main logic of the code is executed before the left and right subtrees, then it is preorder traversal. If the main logic of the code is executed after the left and right subtrees, then it is a post-order traversal. For more detailed content, I will explain in the before and after traversal part of seven tips, everyone first leave an impression and know that there are two ways.
Learning skills of recursive traversal¶
The "One Center" part above introduces a dry goods technique "Two-color Traversal" to unify the three traversal iterative writing methods. The recursive writing of tree traversal is actually okay for most people. Why is it okay to write recursively, but it is a problem to write iteration with stacks? In fact, it is not enough to understand recursion. Lucifer today introduces you to a technique for practicing recursion. In fact, it was mentioned at the beginning of the article, that is, drawing + manual substitution. Some classmates don't know how to draw. Here I will share some ideas about how I learned to draw recursively.
For example, we want to traverse a tree like this in preorder:
The picture is fairly clear, so I won’t explain it much. When you encounter a problem, draw such a recursive graph several times, and you will gradually get a sense of recursion.
Breadth first traversal¶
The two ways of traversing the tree are DFS and BFS. In the DFS just now, we have briefly passed the pre-order and post-order traversal, and have a simple impression of them. In this section, let's look at another tree traversal method-BFS.
BFS is also a kind of algorithm in graph theory. Unlike DFS, BFS uses a horizontal search method and usually uses a queue structure in data structure. Note that DFS is done with the help of the stack, and here is the queue.
BFS is more suitable for finding shortest distance/path and a target of a certain distance. For example, Given a binary tree, find the leftmost value in the last row of the tree., this question is the original question of Likou 513. Isn't this the goal of finding the maximum distance from the root node? A BFS template is solved.
BFS diagram:
(Image from https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/breadth-first-search)
Algorithm flow¶
- Put the root node in the queue first.
- Take the first node from the queue and check if it is the target. -If the target is found, the search ends and the result is returned. -Otherwise, all of its direct child nodes that have not been checked are added to the queue.
- If the queue is empty, it means that the whole picture has been checked-that is, there is no target to be searched in the picture. End the search and return "target not found".
- Repeat step 2.
Algorithm template¶
const visited = {}
function bfs() {
let q = new Queue()
q.push (initial state)
while(q.length) {
let i = q.pop()
if (visited[i]) continue
if (i is the target we are looking for) return result
for (i's reachable state j) {
if (j is legal) {
q.push(j)
}
}
}
return not found
}
Two common categories¶
BFS I currently use two templates, these two templates can solve all the BFS problems of the tree.
I mentioned earlier that "BFS is more suitable for finding shortest distance/path and a target of a certain distance". If what I need to request is the shortest distance/path, I don't care about the first step I go to. At this time, I don't need to mark the target of the layer. And if I need to request all nodes whose distance is equal to k from a certain node, then this information of the first few steps is worthy of being recorded.
Less than k or greater than k is the same.
Marking layer¶
A common BFS template, substituting a question only needs to be fine-tuned according to the question.
class Solution:
def bfs(k):
# Use deque instead of array. Because the time complexity of deleting elements from the head of the array is N, the underlying implementation of the deque is actually a linked list.
queue = collections.deque([root])
# Number of recording layers
steps = 0
# Need to return the node
ans = []
# The queue is not empty, and there is more to life!
while queue:
size = len(queue)
# Traverse all nodes in the current layer
for _ in range(size):
node = queue.popleft()
if (step == k) ans.append(node)
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
# Steps + 1 after traversing all the nodes of the current layer
steps += 1
return ans
Do not mark layers¶
The template without layers is simpler, so you only need to master the goal with layered information.
A common BFS template, substituting a question only needs to be fine-tuned according to the question.
class Solution:
def bfs(k):
# Use deque instead of array. Because the time complexity of deleting elements from the head of the array is N, the underlying implementation of the deque is actually a linked list.
queue = collections.deque([root])
# The queue is not empty, and there is more to life!
while queue:
node = queue.popleft()
# Since the steps are not recorded, we definitely don't need to judge based on the information of the layer. Otherwise, use a template with layers.
if (node is what we want to find) return node
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
return -1
The above are the two basic methods of BFS, namely with layer and without layer. Which one is used depends on whether the question needs to be judged based on the layer information.
Summary¶
The traversal of the tree is the basis of everything that follows, and the two ways of traversing the tree, DFS and BFS, simply come to an end here. Now everyone only needs to know that there are two common methods for DFS and BFS, which I will give later. Everyone will add in detail.
Three question types¶
There are three types of tree questions, namely: search category, construction category and modification category, and the proportion of these three categories is gradually reduced, that is, the search category has the most questions, followed by the construction category, and finally Is the modification class. This is very different from the linked list, which is more of a modified class.
Next, Lucifer will explain these three question types one by one.
Search category¶
The topic of the search category is the absolute bulk of the topic of the tree. There are only two solutions for the search class, namely DFS and BFS, which are introduced below.
Almost all search problems can be easily implemented using recursion. The techniques of recursion will be explained in the single/dual recursion of the seven techniques. There is also a small part that is not easy to implement using recursion. We can use BFS to easily implement it with the help of queues. For example, the most classic is to find the distance between any two points of a binary tree. The distance of the tree is actually the shortest distance, so it can be solved with the BFS template. This is why I said that DFS and BFS are the two basic points of the tree problem.
All search questions only need to grasp three core points, namely start point, end point and target.
DFS Search¶
The basic routine of the DFS search class is to start dfs from the entrance, and then judge whether it is the end point in the dfs. This end point is usually leaf node or empty node. We put * on the topic of ending The boundary of the seven tricks* section introduces, if the target is a basic value (such as a number) to return directly or use a global variable to record, if it is an array, it can be completed by the technique of expanding parameters, about expansion Parameters, will be introduced in the parameter expansion section of **Seven Tips**. This is basically the whole search problem. When you finish reading the next seven tips, it will be clearer when you come back and look at this one.
Routine template:
# Where path is the path of the tree, bring it if you need it, don’t bring it if you don’t need it
def dfs(root, path):
# Empty node
if not root: return
# Leaf node
if not root.left and not root.right: return
path.append(root)
# Logic can be written here, this time is the preorder traversal
dfs(root.left)
dfs(root.right)
# Need to pop up, otherwise it will be calculated incorrectly.
# For example, for the following tree:
"""
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
"""
# If it does not pop, then the path 5 -> 4 -> 11 -> 2 will become 5 -> 4 -> 11 -> 7 -> 2, and its 7 is added to the path by mistake
path.pop()
# Logic can also be written here, this time is the post-order traversal
return the data you want to return
For example, Sword refers to Offer 34. The path where the binary tree neutralizes a certain value This question, the title is: Enter a binary tree and an integer, and print out all paths where the sum of the node values in the binary tree is the input integer. Starting from the root node of the tree and going down to the nodes passed by the leaf nodes form a path.Isn't this all the path from the root node to the end of the leaf node searched out, and the path that selects the sum as the target value? The starting point here is the root node, the ending point is the leaf node, and the goal is the path.
For this kind of problem that satisfies specific and **, we can all conveniently use the form of **preorder traversal + parameter expansion. Regarding this, I will discuss the sequence part of *seven tips *Expand.
Since all paths need to be found, not just one, it is suitable to use backtracking brute force enumeration here. For backtracking, please refer to my Backtracking topic
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
def backtrack(nodes, path, cur, remain):
# Empty node
if not cur: return
# Leaf node
if cur and not cur.left and not cur.right:
if remain == cur.val:
res.append((path + [cur.val]).copy())
return
# Choose
path.append(cur.val)
# Recursive left and right subtree
backtrack(nodes, path, cur.left, remain-cur.val)
backtrack(nodes, path, cur.right, remain-cur.val)
# Cancel selection
path.pop(-1)
ans = []
# Entry, path, and target value are all passed in, where path and path are both extended parameters
backtrack(ans, [], root, target)
return ans
Another example: 1372. The longest interleaved path in a binary tree, title description:
Given you a binary tree rooted at root, the staggered path in the binary tree is defined as follows:
Select any node and a direction (left or right) in the binary tree.
If the forward direction is right, then move to the right child node of the current node, otherwise move to its left child node.
Change the forward direction: left to right or right to left.
Repeat the second and third steps until you can no longer move in the tree.
The length of the staggered path is defined as: the number of nodes visited-1 (the path length of a single node is 0).
Please return the length of the longest interleaved path in the given tree.
such as:
Need to return 3
Explanation: The blue node is the longest interleaved path in the tree (right -> left -> right).
Isn't this all the interleaved paths from any node start to any node end all searched out**, and the longest one is selected? The starting point here is any node in the tree, the end point is also any node, and the goal is the longest interleaved path.
For the problem that the entrance is any node, we can easily use double recursion to complete. Regarding this, I will expand on the single/double recursion part of seven tricks.
For this kind of interlaced problem, a useful technique is to use -1 and 1 to record the direction, so that we can get another direction by multiplying by -1.
886. Possible dichotomy and 785. Judgment bipartition have used this technique.
Expressed in code is:
Here we can solve it by using double recursion. If the problem is limited to only start from the root node, it can be solved with single recursion. It is worth noting that the internal recursion here needs to be cached, otherwise it is easy to cause a timeout due to repeated calculations.
My code is Python, where lru_cache is a cache, you can use your own language dictionary to simulate it.
class Solution:
@lru_cache(None)
def dfs(self, root, dir):
if not root:
return 0
if dir == -1:
return int(root.left != None) + self.dfs(root.left, dir * -1)
return int(root.right != None) + self.dfs(root.right, dir * -1)
def longestZigZag(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.dfs(root, 1), self.dfs(root, -1), self.longestZigZag(root.left), self.longestZigZag(root.right))
It doesn't matter if you don't understand this code, you only need to know the general direction of the search topic. We will introduce the specific method later, and you can leave an impression. More topics and detailed usage of these skills are laid out in the Seven Skills Part.
BFS Search¶
Compared with DFS, this type has significantly fewer questions and fewer routines. Most of the questions are asking for distance. Basically, it can be easily solved by applying the two BFS templates I mentioned above. I won't introduce this much.
Building the class¶
In addition to the search category, the other big head is the construction category. There are two types of construction: ordinary binary tree construction and binary search tree construction.
Ordinary Binary Tree Construction¶
The construction of ordinary binary trees is divided into three types:
- Give you two DFS traversal result arrays, allowing you to construct the original tree structure. For example, the original binary tree is constructed based on the arrays traversed in the first order and traversed later. This kind of question I am in Constructing Binary Tree Series The series is very clear, you can check it out.
This question assumes that the input traversed sequence does not contain repeated numbers, think about why.
- Give you a BFS traversal result array, allowing you to construct the original tree structure.
The most classic is Sword Finger Offer 37. Serialized Binary Tree. We know that all the tree representations of Likou are represented by numbers, and this array is the result of a tree's level traversal, and the child nodes (empty nodes) of some leaf nodes will also be printed. For example: [1,2,3,null,null,4,5], it means a binary tree as follows:
How do we construct the original binary tree based on the result of such a level traversal? This actually belongs to the content of constructing a binary tree, and this type currently focuses on this problem. If you thoroughly understand BFS in this question, then you won't be bothered by it.
- Another is to describe a scenario for you and let you construct a binary tree that meets the conditions. This kind of question is no different from the above, the routine is simply not too similar, such as 654. Maximum Binary Tree, I won’t say more , Everyone will know by practicing this question.
In addition to this static construction, there is also a very rare dynamic construction of binary trees, such as 894. All possible full binary trees ,For this question, just BFS directly. Since there are very few such questions, I won't introduce them too much. As long as everyone masters the most core things, this kind of thing will come naturally.
Construction of Binary Search Tree¶
The reason why the ordinary binary tree cannot be reconstructed according to a sequence is that only the root node is known, and the left and right subtrees cannot be distinguished. If it is a binary search tree, it is possible to construct it according to a traversal sequence. The reason is that the value of the root node of the binary search tree is greater than the value of all the left subtrees, and is less than the value of all the right subtrees. Therefore, we can determine the position of the left and right subtrees based on this feature. After such a conversion, it is no different from the ordinary binary tree above. For example, 1008. Preorder traversal to construct a binary search tree
Modify the class¶
Two common question types are introduced above: search type and construction type. There is also a relatively small proportion of the problem type is the modification category.
Of course, the subject of the modified category is also based on the search algorithm. How to delete it if the target is not found?
There are two basic types of revised questions.
Modification of the subject request¶
One is that the title allows you to add or delete nodes, or to modify the value or point of a node.
It is generally not difficult to modify the topic of the pointer, such as 116. Fill the next right node pointer of each node, isn't this just the way to record the last visited node of the same layer during BFS, and then add a pointer? Regarding BFS, apply my BFS template with layers and it's done.
The topics of adding and deleting are generally slightly more complicated, such as 450. Deleting a node in the binary search tree and 669. Trim Binary Search Tree. In Western France, I will teach you two routines, so you don't have to be afraid of this kind of problem. That is Follow-up traversal + virtual node, these two techniques are also explained in the following seven techniques part. Are you looking forward to the seven techniques? _
In the actual project, we can also not delete the node, but mark the node to indicate that it has been deleted. This is called soft deletion.
Algorithm needs, modify by yourself¶
The other is to add a pointer to facilitate calculations.
For example, 863. All nodes with distance K in a binary tree By modifying the node class of the tree, add A reference to parent points to the parent node, and the problem is transformed into a problem of a certain distance from the target node. At this time, it is solved with the BFS template with layers I mentioned above.
Dynamic languages can directly add attributes (such as the parent above), while static languages are not allowed, so you need to add a new class definition. But you can also use a dictionary to achieve this, the key is the node reference, and the value is what you want to record, such as the parent node here.
For example, for Java, we can:
class Solution {
Map<TreeNode, TreeNode> parent;
public void dfs(TreeNode node, TreeNode parent) {
if (node != null) {
parent.put(node, parent);
dfs(node.left, node);
dfs(node.right, node);
}
}
}
Briefly review the knowledge in this section.
Next are the four important concepts that you have to know about making a tree.
Four important concepts¶
Binary search tree¶
Binary Search Tree (Binary Search Tree), also known as Binary Search Tree.
Binary search tree A binary tree with the following properties:
-If the left subtree is not empty, the values of all nodes on the left subtree are less than the value of its root node; -If the right subtree is not empty, the values of all nodes on the right subtree are greater than the value of its root node; -The left and right subtrees are also binary sort trees respectively; -There is no node with the same key value.
For a binary search tree, the usual operations include insert, search, delete, find the parent node, find the maximum value, and find the minimum value.
Born to find¶
Binary search tree is called search tree because it is very suitable for search.
For example, in the following binary search tree, we want to find the node whose node value is less than and closest to 58. The search process is shown in the figure:
(Picture from https://www.geeksforgeeks.org/floor-in-binary-search-tree-bst/)
It can be seen that every time you go down, a branch will be excluded. If a binary search tree is also a binary balanced tree, the time complexity of the search process is \(O(logN)\). In fact, the essence of the binary search of a balanced binary search tree and the binary search of an ordered array is the same, but the data storage method is different. So why do we need a binary search tree with ordered array dichotomy? The reason is that the structure of the tree is more friendly to dynamic data. For example, the data is frequently changed, such as frequently added and deleted, then a binary search tree can be used. Theoretically, the time complexity of adding and deleting is \(O(h)\), where h is the height of the tree, if it is a balanced binary search tree, then the time complexity is \(O(logN)\). The time complexity of adding and deleting an array is \(O(N)\), where N is the length of the array.
Easy to search, is the original intention of the core of the binary search tree. Preventing the time complexity of the search algorithm from degrading to linear is the original intention of the balanced binary tree.
Many of the dichotomy we usually talk about is the dichotomy of arrays, because arrays can be accessed randomly. However, this dichotomy is too narrow. The essence of dichotomy is to reduce the problem scale to half. Therefore, dichotomy has no essential relationship with data structure, but different data structures give dichotomy with different colors. For example, the jump list is the dichotomy of the linked list, and the binary search tree is the dichotomy of the tree. As you deepen your understanding of algorithms and data structures, you will find more interesting things_
In-order traversal is ordered¶
In addition, the binary search tree has a property, which is very helpful for the problem, that is: The result of the middle-order traversal of the binary search tree is an ordered array. For example, 98. Validate Binary Search Tree can be traversed directly in order, and * *While traversing, judge whether the traversal result is monotonically increasing**, if not, return False in advance.
Another example is 99. Recover Binary Search Tree, the official difficulty is difficult. The main idea is to give you the root node root of the binary search tree, and the two nodes in the tree have been swapped by mistake. Please restore this tree without changing its structure.We can first traverse the nodes that are not incremental, they are the nodes that were exchanged by mistake, and then the exchange can be restored. The difficulty of this question lies in one point, that is, the error exchange may incorrectly exchange the adjacent nodes of the in-order traversal or the non-adjacent nodes of the in-order traversal. These are two cases and need to be discussed separately.
There are many similar topics, so I will not repeat them. If you encounter the search problem of binary search tree, you must first think about whether you can use this property to do it. **
Complete Binary Tree¶
A binary tree with n nodes with a depth of k. The nodes in the tree are numbered from top to bottom and from left to right. If the number of nodes is i (1≤i≤n) and If the node numbered i in a full binary tree has the same position in the binary tree, then this binary tree is called a complete binary tree.
The following is a complete binary tree:
Although there are not many problems to directly investigate the complete binary tree, it seems that there is only one 222. The number of nodes of the complete binary tree (two points can be solved) , But understanding the complete binary tree is actually very helpful for you to do the problem.
As shown above, it is an ordinary binary tree. If I complete the empty nodes, then it is a complete binary tree.
What's the use of this? This is very useful! I summarized two uses:
- We can number the complete binary tree so that the parent and child can be easily calculated by numbering. For example, I number all nodes from left to right and top to bottom, starting from 1. Then it is known that the number of a node is i, then the left child node is 2 _ i, the right child node is 2 _ 1 + 1, and the parent node is (i + 1) / 2.
Students who are familiar with binary heaps may have discovered that this is a binary heap implemented with an array. In fact, a binary heap is an application of a complete binary tree.
Some students will say, "But many topics are not completely binary trees. Isn't that useless?" In fact, we only need to imagine it exists. Can we just fill in the empty node brain? For example, 662. Maximum width of binary tree. Title description:
Given a binary tree, write a function to get the maximum width of the tree. The width of the tree is the maximum width in all layers. This binary tree has the same structure as a full binary tree, but some nodes are empty.
The width of each layer is defined as the length between two endpoints (the leftmost and rightmost non-empty nodes of the layer, and the null nodes between the two ends are also included in the length).
Example 1:
enter:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum value appears at level 3 of the tree, and the width is 4 (5,3,null,9).
It's very simple. A BFS template with layers can be done. It's just a silent question. But there are two points to note here:
-When joining the team, in addition to the ordinary nodes, the empty nodes must be added to the team. -When dequeuing, in addition to the enqueuing node itself, the position information of the node must be enqueued, that is, pos in the code below.
Reference Code:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
q = collections.deque([(root, 0)])
steps = 0
cur_depth = leftmost = ans = 0
while q:
for _ in range(len(q)):
node, pos = q.popleft()
if node:
# Is the node number relationship used?
q.append((node.left, pos * 2))
q.append((node.right, pos * 2 + 1))
# Logic start
if cur_depth != steps:
cur_depth = steps
leftmost = pos
ans = max(ans, pos-leftmost + 1)
# Logical end
steps += 1
return ans
Another example is Sword Finger Offer 37. Serialized Binary Tree. If I serialize a full binary tree form of a binary tree, and then deserialize it through BFS, isn't this the way to use the official serialization tree? such as:
Serialized as "[1,2,3,null,null,4,5]". Isn't this the complete binary tree I just drew? It is to use an ordinary binary tree as a complete binary tree.
Actually, this is not serialized into a complete binary tree, which will be corrected below.
It is very simple to serialize an ordinary tree into a complete binary tree, as long as the empty nodes are treated as ordinary nodes in the queue. Code:
class Codec:
def serialize(self, root):
q = collections.deque([root])
ans =''
while q:
cur = q.popleft()
if cur:
ans += str(cur.val) +','
q.append(cur.left)
q.append(cur.right)
else:
# Except that it is different here, it is the same as ordinary BFS without recording layer
ans +='null,'
# There will be an extra comma at the end, we remove it.
return ans[:-1]
Careful students may find that the code above does not actually serialize the tree into a complete binary tree, which we will talk about later. In addition, the redundant empty nodes in the back are also serialized. This can actually be optimized, and the optimization method is also very simple, that is, remove the null at the end.
As long as you thoroughly understand what I just said, we can number the complete binary tree, so that the parent and child can be easily found by numbering. For example, I number all nodes from left to right and top to bottom, starting from 1. Then it is known that the number of a node is i, then the left child node is 2 _ i, the right child node is 2 _ i + 1, and the parent node is (i + 1) / 2. `This sentence, then deserialization is not difficult for you.
If I use an arrow to indicate the parent-child relationship of a node, and the arrow points to the two child nodes of the node, it looks like this:
We just mentioned:
-No. 2 and No. 3 of the two child nodes of No. 1 node. -No. 4 and No. 5 of the two child nodes of No. 2 node. -. . . -The number 2 * i and the number 2 * 1 + 1 of the two child nodes of node i.
At this point you might write code like this:
def deserialize(self, data):
if data =='null': return None
nodes = data.split(',')
root = TreeNode(nodes[0])
# Start numbering from the first number, and enter the team together with the numbering information
q = collections.deque([(root, 1)])
while q:
cur, i = q.popleft()
# 2 * i is the left node, and the 2 * i number corresponds to the element whose index is 2 * i-1. The same is true for the right node.
if 2 * i-1 <len(nodes): lv = nodes[2 * i-1]
if 2 * i <len(nodes): rv = nodes[2 * i]
if lv !='null':
l = TreeNode(lv)
# Enqueue the left node and its number 2 * i
q.append((l, 2 * i))
cur.left = l
if rv !='null':
r = TreeNode(rv)
# Enqueue the right node and its number 2 * i + 1
q.append((r, 2 * i + 1))
cur.right = r
return root
But the above code is wrong, because when we serialize it is actually not a complete binary tree, which is also the foreshadowing I buried above. Therefore, it will hang if it encounters a case like this:
This is why I said earlier that "the serialization of the above code is not a complete binary tree".
In fact, this is very easy to solve, the core is still the kind of picture I drew above:
In fact, we can:
-Use three pointers to point to the first item, the second item and the third item of the array (if they exist), here are marked with p1, p2, and p3, respectively representing the currently processed node and the left child node of the currently processed node And the right child node of the currently processed node. -p1 moves one bit at a time, p2 and p3 move two bits at a time. -p1.left = p2; p1.right = p3. -Continue the above steps until p1 moves to the end.
So the code is not difficult to write. The deserialization code is as follows:
def deserialize(self, data):
if data =='null': return None
nodes = data.split(',')
root = TreeNode(nodes[0])
q = collections.deque([root])
i = 0
while q and i <len(nodes)-2:
cur = q.popleft()
lv = nodes[i + 1]
rv = nodes[i + 2]
i += 2
if lv !='null':
l = TreeNode(lv)
q.append(l)
cur.left = l
if rv !='null':
r = TreeNode(rv)
q.append(r)
cur.right = r
return root
Although this problem is not a complete binary tree problem, it is very similar to a complete binary tree, and it has a place to learn from a complete binary tree.
Path¶
Regarding the concept of path, leetcode really likes to investigate. If you don’t believe me, go to the official website of leetcode to search for the path and see how many questions there are. There are many variations on the topic of the path of the tree, and it can be regarded as a classic test site.
To understand the concept of path and how to solve this problem, just look at one topic 124. The maximum path sum in a binary tree, although it is difficult difficulty, but if you figure out the concept, it is no different from simple difficulty. Next, we will explain with this question.
The title of this question is Given a non-empty binary tree, return its maximum path sum. The concept of the path is: a sequence that starts from any node in the tree, connects along the parent node-child node, and reaches any node. The path contains at least one node and does not necessarily pass through the root node.This sounds really difficult to understand. I didn't understand the demo given by Likou. Here I drew a few pictures to explain the concept to everyone.
The first are two examples given by the official website:
Then is an example drawn by myself:
The red part in the figure is the node on the maximum path.
As can be seen:
-The path can be made up of one node, two nodes, three nodes, etc., but it must be continuous. -The path must be "straight and straight", and there must be no forks. For example, the lower left corner of the path in the above figure is 3, of course it can also be 2, but 2 is relatively small. However, 2 and 3 cannot be selected at the same time.
Let's go back to question 124. The title says "start from any node..." After reading this description, I will think that the high probability is either the global record maximum value or double recursion.
-If double recursion is used, then the complexity is \(O(N^2)\). In fact, the path sum of the subtree is calculated, and the maximum path sum of the parent node can be derived, so if double recursion is used, there will be repeated calculations . One possible way is to memoize recursion. -If you use the global record maximum, you only need to return the current edge during recursion (not to be turned above), calculate the maximum path sum from the current node inside the function, and update the global maximum. The core here is actually the larger edge of return, because the smaller edge cannot be the answer.
Here I choose to use the second method.
Code:
class Solution:
ans = float('-inf')
def maxPathSum(self, root: TreeNode) -> int:
def dfs(node):
if not node: return 0
l = dfs(node.left)
r = dfs(node.right)
# Select the current node, and select the left and right sides. Of course, the left and right sides can be unselected. Update the global maximum when necessary
self.ans = max(self.ans, max(l,0) + max(r, 0) + node.val)
# Only return to one side, so we pick the larger one to return. Of course, the left and right sides can be unselected
return max(l, r, 0) + node.val
dfs(root)
return self.ans
Similar topic 113. Path Sum I
Distance¶
Similar to the path, the distance is also a similar and frequently occurring test site, and both are test sites for search questions. The reason is that the shortest path is the distance, and the shortest path of the tree is the number of edges.
Practice these two questions, and you will be basically stable when you encounter the distance question.
-834. Sum of Distances in Trees -863. All nodes with distance K in the binary tree
Seven Tips¶
Seven techniques have been mentioned several times above, I believe you can’t wait to see these seven techniques. Let me take out the contents of the bottom of this chapter~
Note that these seven techniques are all based on dfs, bfs only needs to master the template, there are basically no techniques at all.
Those who study hard can find out that only the iterative writing of binary tree (two-color notation)** and **two BFS templates** are practical, and most of the others are strategic thinking. Although algorithmic thinking is important, it must be combined with specific practice to have practical value and to allow us to digest knowledge into our own. And this section is full of practical dry goods ヽ(￣ ω ￣(￣ ω ￣〃)ゝ.
dfs(root)¶
The first technique is also the easiest technique to master. When we wrote the tree topic of Likou, all the input parameters of the function were called root. And this trick is to say that when we write the dfs function, we must also write the formal parameter representing the current node in the function as root. which is:
I have always used to write node before, namely:
Some students may want to ask: "Does this matter?". I summarized two reasons.
The first reason is: In the past, the formal parameter of dfs was written as node, and I often mistakenly wrote root as root, which led to errors (this error is not thrown wrong, so it is not particularly easy to find). This problem has not occurred since I switched to root.
The second reason is: writing in this way is equivalent to using root as a current pointer. At first, the current pointer points to root, and then it continues to modify other nodes pointing to the tree. In this way, the concept is simplified, and there is only the concept of a current pointer. If you use node, there are two concepts of current pointer + root pointer.
(At the beginning, current is root)
(Later current keeps changing. How to change depends on your search algorithm, whether it is dfs or bfs, etc.)
Single/double recursion¶
The above technique is a bit simple, but it is useful. Here is a slightly more difficult technique, which is also more useful.
We know that recursion is a very useful programming technique. Using recursion flexibly can make your code more concise. Conciseness means that the code is not easy to make mistakes. Even if something goes wrong, you can find and fix the problem in time.
Most tree problems can be easily solved with recursion. If one recursion does not work, then come two. (So far I have not seen three recursion or more recursion)
Many people have written about single recursion. In fact, most of the recursion in this article is single recursion. When do you need two recursion? In fact, as I mentioned above, that is If the topic is similar, any node starts with xxxx or all xxx, you can consider using double recursion. But if there are repeated calculations in the recursion, you can use double recursion + memoization or direct single recursion.
For example, Interview Question 04.12. Summation Path, or 563. The slope of the binary tree The title statement of these two questions can be considered using double recursion.
The basic routine of double recursion is a main recursive function and an internal recursive function. The main recursive function is responsible for calculating xxxx starting with a certain node, and the internal recursive function is responsible for calculating xxxx, so that xxxx starting with all nodes is realized.
Where xxx can be replaced with any title description, such as path and etc.
A typical addition double recursion looks like this:
def dfs_inner(root):
# Write your logic here, which is the preorder traversal
dfs_inner(root.left)
dfs_inner(root.right)
# Or write your logic here, that is post-order traversal
def dfs_main(root):
return dfs_inner(root) + dfs_main(root.left) + dfs_main(root.right)
You can use my template to try the above two questions.
Traverse before and after¶
My linked list topic also mentioned the sequence traversal. Since the linked list has only one next pointer, there are only two traversals. The binary tree has two pointers, so there are three common traversals, in addition to the pre-order, there is also a middle-order. In addition to the binary search tree, the middle order is not used much in other places.
Like linked lists, to master the sequence of the tree, you only need to remember one sentence. That is If it is a preorder traversal, then you can imagine that the above nodes have been processed, and you don't have to worry about how to process it. Correspondingly If it is a post-order traversal, then you can imagine that the following tree has been processed, and you don't have to worry about how to process it. The correctness of this sentence is also beyond doubt.
The sequence is more intuitive for linked lists. For the tree, it should be top-down or bottom-up more vividly. Top-down and bottom-up are algorithmically different, and different writing methods sometimes correspond to different writing difficulties. For example https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/, This kind of problem is suitable to be completed by parameter expansion + preorder.
About the technique of parameter expansion, we will expand later.
-Top-down means that at each recursive level, the node is first visited to calculate some values, and these values are passed to the child nodes when the function is called recursively, generally passed to the subtree through parameters in.
-Bottom-up is another common recursive method. It first calls the function recursively on all child nodes, and then gets the answer based on the value of return value and root node itself.
Regarding the thinking skills of sequence, you can refer to my this article The preamble part**.
Summarize my experience:
-Most tree questions are relatively simple to use post-order traversal, and most of them depend on the return value of the left and right subtrees. For example, 1448. Count the number of good nodes in the binary tree -Few problems require pre-order traversal, and pre-order traversal usually combines parameter expansion techniques. For example 1022. Sum of binary numbers from root to leaf -If you can use the parameter and the value of the node itself to determine what should be the parameter passed to its child nodes, then use the preorder traversal. -If for any node in the tree, if you know the answer of its child nodes, you can calculate the answer of the current node, then use post-order traversal. -If you encounter a binary search tree, consider in-order traversal
Virtual Node¶
Yes it is! Not only does the linked list have virtual nodes, but the tree is the same. You may easily overlook this point.
Recall the technique of virtual pointers in linked lists. When do we usually use them?
-One of the cases is that the header of the linked list will be modified. At this time, a virtual pointer is usually needed to make a new head pointer, so there is no need to consider the problem of the first pointer (because the first pointer becomes our virtual pointer at this time, and the virtual pointer does not need to participate in the topic calculation of). The same is true for trees. When you need to modify the head node of the tree (in the tree we call it the root node), you can consider using the virtual pointer technique. -The other is that the question needs to return to a node in the middle of the tree (not the root node). In fact, virtual nodes can also be used. Due to the pointer operation I mentioned above, in fact, you can create a new virtual head, and then let the virtual head disconnect at the right time (just point to the node that needs to be returned), so that we can return to the next virtual head ok.
For more tips on virtual pointers, please refer to this article of the virtual header.
Let's take a look at the two questions in Likou.
[Topic 1] 814. Binary tree pruning¶
Title description:
Given the root node of the binary tree, the value of each node of the tree is either 0 or 1.
Returns the original binary tree with all subtrees that do not contain 1 removed.
(The subtree of node X is X itself and all descendants of X.)
Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red node meets the condition "all subtrees that do not contain 1".
The picture on the right shows the returned answer.
According to the title description, it is not difficult to see that our root node may be removed entirely. This is the situation where the root node is modified I mentioned above. At this time, as long as we create a new virtual node as the new root node, we don't need to consider this issue.
The code at this time is like this:
var pruneTree = function(root) {
function dfs(root) {
// do something
}
ans = new TreeNode(-1);
ans.left = root;
dfs(ans);
return ans.left;
};
Next, only need to improve the dfs framework. The dfs framework is also very easy. We only need to remove the subtree sum of 0 nodes. Calculating the subtree sum is an easy problem. It only needs to traverse once and collect the values.
The code for calculating the subtree sum is as follows:
function dfs(root) {
if (!root) return 0;
const l = dfs(root.left);
const r = dfs(root.right);
return root.val + l + r;
}
With the above foreshadowing, the final code is not difficult to write.
Complete code (JS):
var pruneTree = function(root) {
function dfs(root) {
if (!root) return 0;
const l = dfs(root.left);
const r = dfs(root.right);
if (l == 0) root.left = null;
if (r == 0) root.right = null;
return root.val + l + r;
}
ans = new TreeNode(-1);
ans.left = root;
dfs(ans);
return ans.left;
};
[Topic One] 1325. Delete the leaf node with a given value¶
Title description:
Give you a binary tree rooted at root and an integer target, please delete all leaf nodes whose value is target.
Note that once the leaf node whose value is target is deleted, its parent node may become a leaf node; if the value of the new leaf node also happens to be target, then this node should also be deleted.
In other words, you need to repeat this process until you can no longer delete.
Example 1:
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation:
In the graph on the left above, the green nodes are leaf nodes, and their values are the same as the target (the same is 2), they will be deleted, and the middle graph will be obtained.
A new node becomes a leaf node and its value is the same as target, so it will be deleted again to get the rightmost graph.
Example 2:
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Every step deletes a green leaf node (value 2).
Example 4:
Input: root = [1,1,1], target = 1
Output: []
Example 5:
Input: root = [1,2,3], target = 1
Output: [1,2,3]
prompt:
1 <= target <= 1000
Each tree has a maximum of 3000 nodes.
The range of each node value is [1, 1000].
Similar to the above question, the root node of this question may also be deleted, so here we adopt a similar technique to the above question.
Because the title states **Once the leaf node with the value of target is deleted, its parent node may become a leaf node; if the value of the new leaf node also happens to be target, then this node should also be deleted. In other words, you need to repeat this process until you can no longer delete. ** So it is easier to use post-order traversal here, because if you look at the above description process vividly, you will find that this is a bottom-up process, and bottom-up traversal usually uses post-order traversal.
For the above question, we can decide whether to delete the child node according to the return value of the child node. And this question is to delete self based on whether the left and right subtrees are empty, and the keyword is self. The deletion of the tree is similar to the deletion of the linked list. The deletion of the tree requires the parent node. Therefore, the technique here is similar to that of the linked list. Just record the parent node of the current node and pass it down through parameter expansion. So far, our code is roughly:
class Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
# The singly linked list has only one next pointer, while the binary tree has two pointers left and right, so it is necessary to record which child of its parent node the current node is
def dfs(node, parent, is_left=True):
# do something
ans = TreeNode(-1)
ans.left = root
dfs(root, ans)
return ans.left
With the above foreshadowing, the final code is not difficult to write.
Complete code (Python):
class Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
def dfs(node, parent, is_left=True):
if not node: return
dfs(node.left, node, True)
dfs(node.right, node, False)
if node.val == target and parent and not node.left and not node.right:
if is_left: parent.left = None
else: parent.right = None
ans = TreeNode(-1)
ans.left = root
dfs(root, ans)
return ans.left
Border¶
When I find myself always failing to consider the boundary, we must first know that this is normal and human instinct. To overcome this instinct, you can only overcome it by doing more. Just like changing a bad habit, in addition to persistence, a useful technique is reward and punishment. I have also used this technique.
I have introduced three types of tree questions above. In fact, the focus of boundary consideration is different for different question types. Let's talk about it below.
Search category¶
For search topics, the boundaries of the tree are actually relatively simple. More than 90% of the topic boundaries are in two cases.
Most of the tree topics are search types. Think about how important it is to master these two situations.
- Empty node
Fake code:
def dfs(root):
if not root: print('is an empty node, you need to return a suitable value')
# your code here`
- Leaf nodes
Fake code:
def dfs(root):
if not root: print('is an empty node, you need to return a suitable value')
if not root.left and not root.right: print('It is a leaf node, you need to return a suitable value')
# your code here`
A picture sums it up:
After such processing, the following code basically does not need to be blank.
Building the class¶
Compared with the search class, the construction is more troublesome. I have summarized two common boundaries.
- Boundary of parameter expansion
For example, for question 1008, a binary search tree is constructed according to the preorder traversal. I just think less about the boundary.
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
def dfs(start, end):
if start> end:
return None
if start == end:
return TreeNode(preorder[start])
root = TreeNode(preorder[start])
mid = -1
for i in range(start + 1, end + 1):
if preorder[i]> preorder[start]:
mid = i
break
if mid == -1:
root.left = dfs(start + 1, end)
else:
root.left = dfs(start + 1, mid-1)
root.right = dfs(mid, end)
return root
return dfs(0, len(preorder)-1)
Note that the above code does not judge the case of start == end, just add the following judgment.
- Virtual Node
In addition to searching for classes that can be used to build classes, you can also consider using the virtual nodes I mentioned above.
Parameter expansion method¶
This technique of parameter expansion is very easy to use, once you master it, you will love it.
If parameter expansion is not considered, a simplest dfs is usually as follows:
Sometimes, we need dfs to carry more useful information. There are typically the following three situations:
- Bring information about your father or grandfather.
- Carry path information, which can be a path and a specific path array, etc.
Path and:
def dfs(root, path_sum):
if not root:
# Here you can get the path from root to leaf and
return path_sum
dfs(root.left, path_sum + root.val)
dfs(root.right, path_sum + root.val)
path:
def dfs(root, path):
if not root:
# Here you can get the path from root to leaf
return path
path.append(root.val)
dfs(root.left, path)
dfs(root.right, path)
# Cancel
path.pop()
After learning this technique, you can use Interview Question 04.12. Summation Path to practice your hands.
The above templates are very common, and there are many similar scenarios. In short, when you need to pass additional information to child nodes (keywords are child nodes), be sure to master this technique. This also explains why parameter expansion is often used for pre-order traversal.
- Most of the search questions of the binary search tree need to be expanded for reference, and even how to expand is fixed.
The search of the binary search tree always passes the maximum and minimum values to the left and right subtrees through parameters, similar to dfs(root, lower, upper), and then updates the maximum and minimum values in the recursive process. It should be noted here that (lower, upper) is an interval that is open on both sides.
For example, there is a question 783. Minimum distance between binary search tree nodes is to find the minimum difference of the binary search tree Absolute value. Of course, this problem can also be done with the property that the result of the in-order traversal of the binary search tree is an ordered array as we mentioned earlier. Only one traversal is required, and the smallest difference must appear between two adjacent nodes.
Here I use another method, which is the left and right boundary method in the extended parameter method.
class Solution:
def minDiffInBST(self, root):
def dfs(node, lower, upper):
if not node:
return upper-lower
left = dfs(node.left, lower, node.val)
right = dfs(node.right, node.val, upper)
# Either on the left or on the right, it is impossible to cross (because it is BST)
return min(left, right)
return dfs(root, float('-inf'), float('inf')
In fact, this technique is not only applicable to binary search trees, but also to other trees, such as 1026. Maximum difference between a node and its ancestor, the main idea is: Given the root node root of the binary tree, find the maximum value V existing between different nodes A and B, where V = |A.val-B.val|, And A is the ancestor of B.
Use a routine similar to the one above to solve it easily.
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
def dfs(root, lower, upper):
if not root:
return upper-lower
# Either on the left, on the right, or across.
return max(dfs(root.left, min(root.val, lower), max(root.val, upper)), dfs(root.right, min(root.val, lower), max(root.val, upper )))
return dfs(root, float('inf'), float('-inf'))
return tuple/list¶
Usually, the return value of our dfs function is a single value. And sometimes for the convenience of calculation, we will return an array or primitive ancestor.
For a fixed number, we generally use tuples, and of course the returned array is the same.
**This technique is similar to parameter expansion, except that one works on the function parameters and the other works on the function return value. **
Return to Yuanzu¶
The case of returning tuples is fairly common. For example 865. The smallest subtree with all the deepest nodes, a simple idea is that dfs returns the depth , We locate the answer (the position of the deepest node) by comparing the depth of the left and right subtrees.
Code:
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> int:
def dfs(node, d):
if not node: return d
l_d = dfs(node.left, d + 1)
r_d = dfs(node.right, d + 1)
if l_d >= r_d: return l_d
return r_d
return dfs(root, -1)
But what the title requires to return is the reference of the tree node. At this time, you should consider returning to the original ancestor, that is, in addition to returning the depth, you must also return the node.
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
def dfs(node, d):
if not node: return (node, d)
l, l_d = dfs(node.left, d + 1)
r, r_d = dfs(node.right, d + 1)
if l_d == r_d: return (node, l_d)
if l_d> r_d: return (l, l_d)
return (r, r_d)
return dfs(root, -1)[0]
Return array¶
dfs returns an array relatively rare. Even if the topic requires an array to be returned, we usually declare an array, continue to push during the dfs process, and finally return this array. Instead of choosing to return an array. In most cases, the returned array is used to calculate the Cartesian product. Therefore, when you need to use the Cartesian product, consider using the method of returning an array.
Generally speaking, it is easier to see if you need to use Cartesian product. Another less accurate technique is that if the title has "all possible" and "all situations", you can consider using this technique.
A typical topic is 1530. Number of good leaf node pairs
Title description:
Give you the root node of the binary tree root and an integer distance.
If the shortest path length between two leaf nodes in the binary tree is less than or equal to distance, then they can form a good pair of leaf nodes.
Returns the number of good leaf node pairs in the tree.
Example 1:
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4, and the length of the shortest path between them is 3. This is the only good pair of leaf nodes.
Example 2:
Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: Good leaf node pairs are [4,5] and [6,7], and the shortest path length is both 2. But the pair of leaf nodes [4,6] does not meet the requirements, because the shortest path length between them is 4.
Example 3:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good leaf node pair is [2,5].
Example 4:
Input: root = [100], distance = 1
Output: 0
Example 5:
Input: root = [1,1,1], distance = 2
Output: 1
prompt:
The number of nodes of tree is in the range of [1, 2^10].
The value of each node is between [1, 100].
1 <= distance <= 10
We learned the concept of path above, and used it again in this question.
In fact, the shortest path (distance) between two leaf nodes can be calculated with the nearest common ancestor. That is, The shortest path between two leaf nodes = the distance from one of the leaf nodes to the nearest common ancestor + the distance from the other leaf node to the nearest common ancestor.
Therefore, we can define dfs(root), whose function is to calculate the distance to each leaf node with root as the starting point. If its child node has 8 leaf nodes, then an array of length 8 is returned, and the value of each item in the array is the distance from the corresponding leaf node.
If the result of the subtree is calculated, then the parent node only needs to add 1 to each item in the subtree. This is not difficult to understand, because ** the distance from the parent to each leaf node is the distance from the parent node to the child node (1) + the distance from the child node to each leaf node**.
From the above derivation, we know that we need to calculate the information of the subtree first, so we choose pre-order traversal.
Complete code (Python):
class Solution:
def countPairs(self, root: TreeNode, distance: int) -> int:
self.ans = 0
def dfs(root):
if not root:
return []
if not root.left and not root.right:
return [0]
ls = [l + 1 for l in dfs(root.left)]
rs = [r + 1 for r in dfs(root.right)]
# Cartesian Product
for l in ls:
for r in rs:
if l + r <= distance:
self.ans += 1
return ls + rs
dfs(root)
return self.ans
894. All possible full binary trees is the same routine, everyone use the above knowledge to practice~
Classic topic¶
It is recommended that you do all the topics mentioned in this article first, and then use the knowledge gained in this literature to do the following ten exercises to check your learning results!
-Sword refers to Offer 55-I. The depth of the binary tree -Sword refers to Offer 34. The path where the binary tree neutralization is a certain value -101. Symmetric Binary Tree -226. Invert Binary Tree -543. Diameter of Binary Tree -662. Maximum width of binary tree -971. Flip the binary tree to match preorder traversal -987. Vertical Order Traversal of Binary Tree -863. All nodes with distance K in the binary tree -Interview Question 04.06. Successor
to sum up¶
One of the central points of the tree title is traversal, which is the basis for searching and modifying problems.
The traversal is divided into breadth-first traversal and depth-first traversal from the general direction. These are our two basic points. The two basic points can be further subdivided, such as breadth-first traversal with and without layer information (in fact, as long as the layer information is enough). Depth-first traversal is common in pre-order and post-order, middle-order is mostly used in binary search tree, because the middle-order traversal of binary search tree is a strictly increasing array.
From a general perspective, there are three types of tree topics. One is search. This type of topic is the most. This type of topic firmly grasps the starting point, ending point and goal. I have talked about the topic of the construction type before. The one-sentence summary is to determine the position of the root node according to one traversal result, and determine the left and right children according to another traversal result (if it is a binary search tree) tree. There are not many modified types of questions. This problem boundary requires special consideration. This is the essential difference from the search problem. You can use the virtual node technique. In addition to the search problem, virtual nodes can also be considered if the return value is not the root node.
Trees have four more important concepts that are very helpful to the problem. They are complete binary tree, binary search tree, path and distance. It is recommended that you do a good job of related topics. They are all classics.
Finally, I introduced you to seven dry goods techniques, many of which explain under what circumstances they can be used. If you want to use it yourself, find a few questions and try it.
The above is the whole content of the tree topic. If you have any thoughts on this, please leave me a message. I will check the answers one by one when I have time. More algorithm routines can visit my LeetCode problem solution warehouse: https://github.com/azl397985856/leetcode. Currently it has 38K stars. You can also pay attention to my public account "Like Plus" to take you to the hard bones of algorithm.
The 1,000-page e-book that I have compiled has been developed and downloaded. You can go to the backstage of my public account "Likoujiajia" and reply to the e-book to get it.
