zero
Brush question review progress
Hello, I’m Johngo!
This article is the third in the “Through Trees” series and is a top-down summary of such topics in the “Trees” program.
Brush together the small partners, the disc or to nag, record ideas, in the process of recording, once again deep experience!
Let’s take a look at the progress of this article.
Basically, the vast majority of tree topics have a very large “top down” category.
What do you mean? When you compute the result, you usually do it from the root to the leaf, like the maximum depth, the sum of paths, all the paths from the root to the leaf, and so on, and so on, and so on, and so on.
The topics involved
104. Maximum depth of binary tree: leetcode-cn.com/problems/ma…
112. Total path: leetcode-cn.com/problems/pa…
113. Total path II: leetcode-cn.com/problems/pa…
437. Total path III: leetcode-cn.com/problems/pa…
257. All paths of binary tree: leetcode-cn.com/problems/bi…
129. Find the sum of the numbers from the root to the leaf: leetcode-cn.com/problems/su…
988. Minimum string from a leaf: leetcode-cn.com/problems/sm…
Then there are basically two kinds of solutions to these problems:
The first category: BFS, breadth first search, using the hierarchical traversal method to solve
The second type: DFS, depth first search, the use of the first in order to traverse the tree to solve the problem
Since we are on BFS first, let’s start with BFS first and then describe the solution to DFS later.
one
BFS ideas
BFS (Breadth First Search) : Breadth First Search
Just to recall the classical binary tree sequence traversal problem, let me show you the graph that I need.
It’s a very simple process. Loop to determine if there is an element in the queue. If so, access the element and determine if there are children of the element. If so, the children will be queued in turn.
Let’s look at the code again:
res = []
while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)
Copy the codeVery smooth very classic a level of traversal code.
Now you want to throw in two quotes, add a little seasoning to the code above, and see if it can be solved easily.
Quotes a
Can we record some information from the root node to the current node during the traversal?
Include:
1, the root node to the current node path information
2, the path from the root to the current node
The letters in the nodes in the above figure correspond to numbers to meet the requirements in example 1. See the following figure:
In the process of traversal, the node value (including node object, path from root to current node, path from root to current node and) is continuously recorded.
Node represents the node object
Node_path indicates the path from the root node to the current node
Node_val indicates the path sum from the root node to the current node
(node, node_path, node_val)
Code implementation:
res = []
while queue:
node, node_path, node_val = queue.pop()
res.append((node, node_path, node_val))
if node.left:
queue.appendleft((node.left, node_path+str(node.left), node_val+node.left.val))
if node.right:
queue.appendleft((node.right, node_path+str(node.right), node_val+node.right.val))
Copy the codeIn this way, the triplet information is carried at all times during the traversal. Perfect solution!
Quotes two
Can I carry a value to record the sequence during sequence traversal?
Yeah, that’s it, using an extra variable to record the sequence.
This train of thought, actually very easy to let me think of binary tree according to LeetCode form before printing a process (don’t remember friend can view mp.weixin.qq.com/s/MkCF5TaR1… Recall the sequence traversal of LeetCode)
Below I also put LeetCode requirements in the hierarchical traversal of the graphical process put out, as a recall reference!
“Click the image below to view the original hd image” 👇
That is, node_depth+=1 is performed at each level of traversal. Let’s see what the original code looks like (and… Remember ~?) :
def levelOrder(self, root) :
res = []
if not root:
return res
queue = [root]
while queue:
level_queue = [] # Temporarily record each layer node
level_res = [] Temporarily record the node value of each row
for node in queue:
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res
Copy the codeAt each level of traversal, the queue is given a new queue, level_queue, which is the set of all nodes in the new level.
Based on this idea
First, the initialization variable is used to record the sequence value node_depth = 0
Next, node_depth+=1 after each while queue:
And then the value of node_depth is what you want for that particular level
Look at the implementation after a few code changes
def levelOrder(self, root) :
res = []
# Sequence record
node_depth = 0
if not root:
return res
queue = [root]
while queue:
node_depth += 1 # Sequence value +1
level_queue = []
level_res = []
for node in queue:
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res
Copy the codeHa ha yes, don’t look! It’s the two lines that are commented out, but the node_depth is whatever you want.
For example, the maximum depth calculation, which is the final node_depth value; If the path from the root to the node is the same as the target you gave, it is the node_depth of the order in which the node is located.
Good!
Two important questions were raised, there is no feeling, is it really a simpler idea. Let’s see what these simple ideas can do!
Use the above “quote 1” and “quote 2” ideas for examples to see how to help some of the titles in LeetCode?
LeetCode104. The maximum depth of a binary tree
Title link: leetcode-cn.com/problems/ma…
GitHub answer: github.com/xiaozhutec/…
In fact, “quote 2” carries a value to record the sequence, and finally returns node_depth which is the maximum depth of the binary tree!
def maxDepth_bfs(self, root) :
if not root:
return 0
queue = collections.deque()
# Initialize depth to 0
node_depth = 0
Initialize the node element root in the queue
queue.appendleft(root)
while queue:
# Each layer traversal, depth +1
node_depth += 1
Record the set of nodes at each level
level_queue = []
for node in queue:
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
return node_depth
Copy the codeIs it easy to solve!
Here’s another one:
LeetCode112. Total path:
Title link: leetcode-cn.com/problems/pa…
GitHub answer: github.com/xiaozhutec/…
The LeetCode112 question is from the root node to the leaf node, is there a path and a path for target.
As shown in the figure below, if we want to find a path whose path and target=16, we can easily judge that the path in the triplet (9, 1->2->4->9, 16) in the last node is 1->2->4->9 by using the idea in “Example 1”.
The code is also easy to implement
def hasPathSum_bfs(self, root, targetSum) :
if not root:
return False
queue = [(root, root.val)]
while queue:
node, node_sum = queue.pop(0)
if not node.left and not node.right and node_sum == targetSum:
return True
if node.left:
queue.append((node.left, node_sum+node.left.val))
if node.right:
queue.append((node.right, node_sum+node.right.val))
return False
Copy the codeIf you want to return the path, you can just return the path!
Here’s another one:
LeetCode257. All paths of the binary tree:
Title link: leetcode-cn.com/problems/bi…
GitHub answer: github.com/xiaozhutec/…
I’m going to go through all the paths from the root to the leaves. It’s the same idea as in Example 1, when you go through the leaves, you take the path values of all the triples in the leaves. For example, the path in the leaf node (9, 1->2->4->9, 16) is 1->2->4->9.
A set of paths can be obtained:
[[1->3->6], [1->3->7], [1->2->4->8], [1->2->4->9]]
Copy the codeThe code is very similar
def binaryTreePaths_bfs(self, root) :
res = []
if not root:
return res
queue = collections.deque()
queue.appendleft((root, str(root.val)+"- >"))
while queue:
node, node_val = queue.pop()
if not node.left and not node.right:
res.append(node_val[0: -2])
if node.left:
queue.appendleft((node.left, node_val + str(node.left.val) + "- >"))
if node.right:
queue.appendleft((node.right, node_val + str(node.right.val) + "- >"))
return res
Copy the codeThe core is to record the record of the path in the process of traversal, and finally get the desired result!
Here’s one last example:
LeetCode129. Find the sum of numbers from root to leaf
Title link: leetcode-cn.com/problems/su…
GitHub answer: github.com/xiaozhutec/…
This topic still continues the idea in “Quote 1”, that is, the number in the path is recorded at a time, converted into a number, and then added.
Path, respectively, for instance, the picture [[1 – > 3 – > 6], [1 – > 3 – > 7), (1 – > 2 – > 4 – > 8], [1 – > 2 – > 4 – > 9]], the corresponding figures for [10, 11, 15, 16], so the sum of Numbers for 10 + 11 + 15 + 16 = 52.
The last problem was to iterate through the paths, this problem just adds one more step, which is to turn each path into a number and add them up.
def sumNumbers_bfs(self, root) :
res = []
sum = 0
if not root:
return 0
queue = collections.deque()
queue.append((root, str(root.val)))
while queue:
node, node_val = queue.pop()
if node and not node.left and not node.right:
res.append(node_val)
if node.left:
queue.appendleft((node.left, node_val+str(node.left.val)))
if node.right:
queue.appendleft((node.right, node_val+str(node.right.val)))
for item in res:
sum+ =int(item)
return sum
Copy the codeThis is the final step, converting the numeric strings in the array to integers and adding them up. Get the final result!
There are a few other similar topics, but I won’t mention them here. The “top down” topics given at the beginning of this article are on Github: github.com/xiaozhutec/… On the record, the details of the code can refer to.
About this part of the topic, the focus is to say that “quote a” and “quote two” two aspects of the train of thought, the two aspects of the train of thought can be the vast majority of this kind of problem can be solved!
The following is a summary of the use of DFS to solve the problem.
two
DFS ideas
Depth First Search (DFS) : Depth First Search
Recall the recursive traversal of binary trees, which is also the idea of DFS. In this article in detail before mp.weixin.qq.com/s/nTB41DvE7…
Recursive traversal of binary trees, very simple but not very easy to understand. I’ve talked a little bit about how to understand this before.
A lot of times I’m going to use a very easy idea, which is to take the recursive traversal of a binary tree and use it to understand and solve problems at the leaves of the binary tree and up.
Let’s first look at the code for each iteration.
Preorder traversal of a binary tree:
def pre_order_traverse(self, head) :
if head is None:
return
print(head.value, end="")
self.pre_order_traverse(head.left)
self.pre_order_traverse(head.right)
Copy the codeBinary tree in order traversal:
def in_order_traverse(self, head) :
if head is None:
return
self.in_order_traverse(head.left)
print(head.value, end="")
self.in_order_traverse(head.right)
Copy the codeSubsequent traversal of a binary tree:
def post_order_traverse(self, head) :
if head is None:
return
self.post_order_traverse(head.left)
self.post_order_traverse(head.right)
print(head.value, end="")
Copy the codeAfter reading this code, it’s nice and clean, but it’s really not very readable…
The next issue, will analyse the issue of rectified trees | the top-down subject project “, and the issue of “top-down” title, ideas will also be some differences.
This first “from the top down” this kind of topic using THE idea of DFS to say clear!
Using binary tree recursive thinking, in fact, it is very easy to solve this kind of problem, the BFS to say the problem with DFS ideas to solve, the code looks more concise, beautiful!
LeetCode104. The maximum depth of a binary tree
Title link: leetcode-cn.com/problems/ma…
GitHub answer: github.com/xiaozhutec/…
Simple to exasperate, understand to want to hit people!
def maxDepth_dfs(self, root) :
if not root:
return 0
else:
max_left = self.maxDepth_dfs(root.left)
max_right = self.maxDepth_dfs(root.right)
return max(max_left, max_right) + 1
Copy the codeIt’s so easy! ~ ~
A follow-up traversal, which solves the problem in no time!
Since we are using recursive calls, let’s start with the leaves:
If self.maxdepth_dfs (root.left) and self.maxdepth_dfs (root.right) recurse, return 0; if self.maxdepth_dfs (root.
If self.maxdepth_dfs (root.left) or self.maxdepth_dfs (root.right) returns Max (max_left, max_right) + 1, if self.maxdepth_dfs (root.left) returns Max (max_left, max_right) + 1, if self.maxdepth_dfs (root.right) returns Max (max_left, max_right) + 1, if self.maxdepth_dfs (root. Is the return value of [a.] 0+1.
Through the above [A. B.] two-point lock structure ideas for code design, must be correct.
【 B.】, is not too easy to understand, the heart to think, suddenly understand the time, really clever!
Next topic:
LeetCode112. Total path:
Title link: leetcode-cn.com/problems/pa…
GitHub answer: github.com/xiaozhutec/…
The LeetCode112 problem is to find a path from the root node and a path for target.
Here’s another example of too simple code:
def hasPathSum(self, root, targetSum) :
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
Copy the codeThe value of the targetSum is recursively subtracted from each node until it reaches a leaf node. That is, the path exists.
The above is a very neat sequence traversal procedure.
Since we are using recursive calls, we will start with the leaves:
A. When recursion to the leaf, the program determines whether the value of the leaf node and the remaining value of tagetSum are equal;
Left, targetSum – root.val) and self. HasPathSum (root.right, targetSum – root.val). The return value is the value returned by [a.].
Here’s another one:
LeetCode257. All paths of the binary tree:
Title link: leetcode-cn.com/problems/bi…
GitHub answer: github.com/xiaozhutec/…
This problem is solved with DFS, which is also very concise, but there is an extra step record in the middle, so there will be a few more lines of code:
def binaryTreePaths_dfs(self, root) :
res = []
if not root:
return res
def dfs(root, path) :
if not root:
return
if root and not root.left and not root.right:
res.append(path + str(root.val))
if root.left:
dfs(root.left, path + str(root.val) + "- >")
if root.right:
dfs(root.right, path + str(root.val) + "- >")
dfs(root, "")
return res
Copy the codeThe core is still a recursive first order traversal, still let’s use recursive solution steps to analyze:
A. When recursion to the leaf, there is no left or right child, directly add the node to the path;
DFS (root.left, path + STR (root.val) + “->”) and DFS (root.right, path + STR (root.val) + “->”) The value of the current node is added to the path.
Or in accordance with this idea, you can easily solve the problem!
Here’s one last example:
LeetCode129. Find the sum of numbers from root to leaf
Title link: leetcode-cn.com/problems/su…
GitHub answer: github.com/xiaozhutec/…
This problem is similar to the previous problem, which is to add the calculated path values to integers. Look at the code:
def sumNumbers_dfs(self, root) :
res = [] # Set of all paths
sum = 0 # Sum of all paths
def dfs(root, path) :
if not root:
return
if root and not root.left and not root.right:
res.append(path + str(root.val))
if root.left:
dfs(root.left, path + str(root.val))
if root.right:
dfs(root.right, path + str(root.val))
dfs(root, "")
for item in res:
sum+ =int(item)
return sum
Copy the codeThe core essence is a recursive implementation of the first order traversal, and I won’t go through the two steps, refer to the last problem.
B: well.. Probably this “tree – from the top down” has been close to the end, looking for brush topic organization friends can participate in together, private message I OK! Let’s stick together!
three
Sum up a few words
Personal brush problem experience, it is inevitable that there will be a lack of thinking, if we have found, must be put forward, exchange and study together!
The “tree-top-down” problem is suitable for both BFS and DFS.
When using BFS to solve problems, the idea is clear, the code will look a little bit more!
However, in the case of DFS, the code is concise, but the idea is sometimes a little confused, and it takes a lot of practice to gradually become clear!
The next issue is rectified trees | not top-down project “, specifically about “tree – a top-down” this category, don’t know will have the final checking of the period, the ideas and decide.
The code and documentation for this article are at github.com/xiaozhutec/… Star. Thank you!