Pre-reading bonus: Hundreds of Internet technology books for you
Share a LeetCode title every day
5 minutes a day, progress together
LeetCode N tree sequence traversal, address: leetcode-cn.com/problems/n-…
The tree node class
class Node(object) :
def __init__(self, val=None, children=[]) :
self.val = val
self.children = children
Copy the codeThe special thing about an n-fork tree is that a node may contain N nodes, so the children of each node are set to an array
Sequence traversal
Sequencing traversal is, for the most part, something that is often asked in interviews.
And in particular, there’s a little dot here, which might give you a little bit of a pinch, which is how you print the nodes.
For example, the structure of a tree is:
A
/ | \
B C D
/|\ / \
E F G H I
Copy the codeThe results can be printed in one of two ways:
One is normal traversal, direct printing
The other is to print the elements in each level individually, which is also the format required by LeetCode429
# the first
['A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I']
# the second
[['A'], ['B'.'C'.'D'], ['E'.'F'.'G'.'H'.'I']]
Copy the codeThe first is simple, and the second may require a little recording of intermediate results. Let’s break them up…
The first kind of sequence traversal
1. Initialize result set RES, initialize queue, and place the root node in queue.
2. As long as the queue is not empty, loop traversal, each traversal will prevent the first element into the RES, and then the children of the first element into the queue in turn;
3. Loop through point 2.
Look at the code:
def levelOrder_basic(self, root) :
# Initialize result set res
res = []
Initialize the queue and place the root node in the queue
queue = collections.deque()
queue.appendleft(root)
while(queue):
# prevent the first element from entering the RES on each iteration
pop_node = queue.pop()
res.append(pop_node.val)
Join the children of the first element in the queue
for node in pop_node.children:
queue.appendleft(node)
return res
Copy the codeIn fact, it is relatively simple, is to put the traversal to the node to the result set, at the same time, the child node of the node into the team, and then the loop is good!
The second kind of sequence traversal
The difficulty with this kind of traversal is that you have to put each level of elements into an array, and then put each level of arrays into the final array
Like this:
[['A'], ['B', 'C', 'D'], ['E', 'F', 'G', 'H', 'I']]
Copy the codeSimilar to the first kind of sequential traversal, the only change is that the elements at each level are traversed individually
1. Initialize result set RES, initialize queue, and place the root node in queue.
(Note: this queue is for each level of the node element. If you don’t understand, read on.)
2. As long as the queue is not empty, loop through and initialize both temporary arrays simultaneously
The first one, tmp_res = [], temporarily stores the nodes accessed by each layer of traversal, which will eventually be merged into the result RES
The second, tmp_queue = [], temporarily stores node elements at the next level for the next loop
Each iteration will prevent the first element from entering tMP_RES, and then the children of the first element will be queued to tmp_queue
Finally, tmp_queue is assigned to queue and tmp_RES is merged into the final result set res
3. Loop through point 2 until the queue is empty
4. Return the final result set res
Look at the code
def levelOrder(self, root) :
# Final result
res = []
if not root:
return res
Initialize the queue and place the root node in the queue
# store nodes at each level
queue = collections.deque()
queue.appendleft(root)
while(queue):
# Temporarily store the queue of nodes and finally merge them into the final RES
tmp_res = []
Temporarily store the next layer of nodes in the queue
tmp_queue = []
for node in queue:
tmp_res.append(node.val)
# Place children in tmp_queue
for child_node in node.children:
tmp_queue.append(child_node)
# assign tmp_queue to queue and tmp_res to the final result set res
queue = tmp_queue
res.append(tmp_res)
Copy the codeIt’s a little bit complicated, but the point is, instead of just looping through the queue, we’re dynamically assigning each layer to the queue, which means that every time we loop through the queue, the value in the queue is the set of nodes at the current layer.
Just draw a picture and it will look easy!
All the code
# -*- coding:utf-8 -*-
# !/usr/bin/env python
import collections
# Tree class
class Node(object) :
def __init__(self, val=None, children=[]) :
self.val = val
self.children = children
class Solution(object) :
def levelOrder_basic(self, root) :
"" "base sequence traversal, is to make each layer node values one-time print it out Similar to the 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] this: param root: : return: "" "
res = []
queue = collections.deque()
queue.appendleft(root)
while(queue):
pop_node = queue.pop()
res.append(pop_node.val)
for node in pop_node.children:
queue.appendleft(node)
return res
def levelOrder(self, root) :
"" "sequence traversal (LeetCode specified in the format), where each layer of the node into their respective array is similar to [[' A '], [' B ', 'C', 'D'], [' E ', 'F', 'G', 'H', 'I']] : param root: :return: """
# Final result
res = []
if not root:
return res
Initialize the queue and place the root node in the queue
# store nodes at each level
queue = collections.deque()
queue.appendleft(root)
while(queue):
# Temporarily store the queue of nodes and finally merge them into the final RES
tmp_res = []
Temporarily store the next layer of nodes in the queue
tmp_queue = []
for node in queue:
tmp_res.append(node.val)
# Place children in tmp_queue
for child_node in node.children:
tmp_queue.append(child_node)
queue = tmp_queue
res.append(tmp_res)
return res
if __name__ == "__main__":
# Create new node
root = Node('A')
node_B = Node('B')
node_C = Node('C')
node_D = Node('D')
node_E = Node('E')
node_F = Node('F')
node_G = Node('G')
node_H = Node('H')
node_I = Node('I')
# Build a trinomial tree
# A
# / | \
# B C D
# / | \ \
# E F G H I
root.children = [node_B, node_C, node_D]
node_B.children = [node_E, node_F, node_G]
node_D.children = [node_H, node_I]
s = Solution()
print(s.levelOrder_basic(root))
print(s.levelOrder(root))
Copy the codeCan execute directly ha!