1 introduction
Hi, the tree has been a brush for a while.
There was a delay in time. We have summarized the basic traversal of “tree” before, this article will look at the specific topic, for the basic traversal can encounter some problems.
Below are some of the “basic traversal” problems we defined earlier.
Around the applicability of the front and back order traversal for the n-fork tree, the different printing methods have been sequentially traversed, what are the points to pay attention to.
The title is as follows:
102. Sequential traversal of binary trees leetcode-cn.com/problems/bi…
589.N Preorder traversal of a cross tree leetcode-cn.com/problems/n-…
107. Sequential Traversal of binary trees II leetcode-cn.com/problems/bi…
145. Back-order traversal of binary trees leetcode-cn.com/problems/bi…
94. Binary tree in order traversal leetcode-cn.com/problems/bi…
429. Sequential traversal of N cross trees leetcode-cn.com/problems/n-…
144. preorder traversal of binary tree leetcode-cn.com/problems/bi…
590. Back-order traversal of N cross trees leetcode-cn.com/problems/n-…
Above, recorded on Github: github.com/xiaozhutec/…
2 classification
Front we said some basic tree traversal, direct links: mp.weixin.qq.com/s/nTB41DvE7…
Based on the previous basis, it is very intuitive to divide the above traversal problems into two categories and two aspects
Two types: the first type, which is preordered traversal, in-order traversal and subsequent traversal. The second type, hierarchical traversal two aspects: the first, recursive implementation, which is suitable for pre-order traversal, in-order traversal and subsequent traversal. The second aspect, non-recursive implementation is suitable for pre-order traversal, in-order traversal, subsequent traversal and hierarchical traversal
3 Recursive traversal
In the previous mp.weixin.qq.com/s/nTB41DvE7… The recursion method has been described in detail in an article of The University of New York.
Then this article involves the traversal method of n-fork tree, so we compare the code design of binary tree and n-fork tree. Due to their similarity, it is easy to solve these problems
First, define “tree” node class, binary tree and N – fork tree node definition difference
# binary tree
class TreeNode(object) :
def __init__(self, val, left=None, right=None) :
self.val = val
self.left = left
self.right = right
# N fork tree
class Node(object) :
def __init__(self, val=None, children=[]) :
self.val = val
self.children = children
Copy the codeIt looks like the difference between the left and right children of a binary tree and the children of an n-fork tree, but it’s essentially the same thing, and the left and right children of a binary tree can also be written as a list of children.
That is:
# binary tree
class TreeNode(object) :
def __init__(self, val, children=[]) :
self.val = val
self.children = children
Copy the codeAnd here the children of the binary tree has only two children, left and right.
Having described the definition of children above, let’s look at the recursive traversal.
# binary tree
res = []
def pre_order(root) :
if not root:
return
res.append(root.val)
pre_order(root.left)
pre_order(root.right)
# N fork tree
res = []
def pre_order(root) :
if not root:
return
res.append(root.val)
for node in root.children:
pre_order(node)
Copy the codeSee the difference? The difference is in the code after res.append(root.val).
A binary tree is written by recursing the left child and then recursing the right child.
And the way you write an n-fork tree is you recurse the children one by one, using a for loop.
So, the difference is the way recursion is written, binary tree recursion twice, n-tree recursion N times
It’s the same logic, isn’t it simple. It’s kind of like a first order traversal, where the first order traversal and the next order traversal are handled by the same logic (N cross tree, N equals 2 to N).
Github: github.com/xiaozhutec/…
4 non-recursive traversal
Non-recursive traversal sequence, in sequence, and the subsequent first traversal of logic in detail also has written here, can return to a head to see mp.weixin.qq.com/s/nTB41DvE7…
Level traversal in the “tree – top-down” category, using more compared with the recursive method, using hierarchical traversal is more easy to understand, and the code framework is a single, detailed introduction and case will be my next the rectified trees | top-down category subject project “in.
The non-recursive traversal in this paper is mainly aimed at the hierarchical traversal. So why is it clearer than it was before?
Well, the level traversal that we talked about earlier, the way that we print it out is a little bit different than the way that we print it out in the LeetCode problem. And just because of the difference in printing, it will lead to a different way of thinking, which will be encountered in many cases later.
As follows:
# Classic hierarchical traversal print form
['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I']
Print form in # LeetCode
[['A'], ['B'.'C'.'D'], ['E'.'F'.'G'.'H'.'I']]
Copy the codeYes, the form printed in LeetCode requires that each layer of node elements be placed in a separate list, and then in a larger list.
Traditional hierarchical traversal printing form
Just a quick review of the traditional way of printing.
Follow the description in the picture above and draw it with your hands. It will be very simple.
To sum it up:
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.
Look at the code:
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 codeIt is to judge whether there are enough elements at the head of the queue, if there are elements, access the node element, and judge whether the node has children, if there are, then enter the queue in turn. Continue the circular judgment.
In fact, in the case of an n-cross tree, it’s the same logic, except you take the two kids in the binary tree, and you replace them with N kids, and you queue them up.
while queue:
node = queue.pop()
res.append(node.val)
for child_node in node.children:
queue.appendleft(child_node)
Copy the codeSame thing! Is it simple?
How titles are printed in LeetCode
It is also described by a graph. Compared to the classic hierarchy traversal, storing each layer separately is a little more complicated and requires a little change of thinking.
Core sentence
Queue is the set of nodes at the current level, and level_queue is the set of nodes at the next level.
Each time we iterate through the nodes in the current level queue, we write that level’s set of nodes into a temporary list and queue the nodes at the next level into level_queue. Then assign level_queue to queue and loop until queue is empty.
Finally, each level of temporary list is written into a larger list
“Click the image below to view the original hd image” 👇
The above figure is a binary tree for example, in fact, and N fork tree logic is almost the same, let’s first look at the binary tree related core code:
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: Loop through all nodes at each level
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 codeIn a similar vein, consider the hierarchy traversal code for an n-fork tree:
def levelOrder_leetcode(self, root) :
res = []
queue = [root]
if not root:
return res
while queue:
level_queue = [] Save each layer node element temporarily for the next iteration
level_res = [] # Temporarily save the values of each layer
for node in queue:
level_res.append(node.val)
if node.children:
for child_node in node.children:
level_queue.append(child_node)
queue = level_queue
res.append(level_res)
return res
Copy the codeAt this point, you should be familiar with some of the differences between binary and n-fork trees, which are still a few lines of code after level_res.append(node.val).
The purpose of this article is to explain some of the core solutions to the basic “tree traversal” on LeetCode described at the beginning.
The code and documentation for this article are at github.com/xiaozhutec/… , you can download the code to run!
Github content has just started to be updated, so those interested can join us to learn. Private message I “LeetCode brush problem” group brush problem progress together.
If you have star in hand, you can help me point star when you are free. Thank you!