如何只用一条线遍历一棵树?(python，树遍历)

Question

对于二叉树，我们可以像这样在一行中遍历它(有序、预序、后序都可以(：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# this is a preorder traversal with one line:
class Solution:
def preorderTraversal(self, root) -> List[int]:
return [] if root is None else [r.val] + self.preorderTraversal(r.left) + self.preorderTraversal(r.right)

对于一个节点中有多个子节点的树，如何在一行中完成遍历工作？我认为列表理解是一种可能的方法，但我不能一行完成这项工作。

"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if root is None: return []
ans = [root.val]
[ans.extend(x) for x in [self.preorder(child) for child in root.children]]
return ans
# This is a normal traversal:
# class Solution:
#     def preorder(self, root: 'Node') -> List[int]:
#         if root is None: return []
#         ans = [root.val]
#         for child in root.children:
#             ans += self.preorder(child)
#         return ans

Answer 1

使用列表理解来收集根的所有子项的遍历，无论有多少子项。

class Solution:
def preorderTraversal(self, root) -> List[int]:
# Original hard-coded approach for binary trees
# return [] if root is None else [r.val] 
#   + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
# Generalized approach for binary trees
# return [] if root is None else [r.val] 
#   + [y for child in [root.left, root.right] for y in self.preorderTraversal(child)]
# Generalized approach for a tree with arbitrary children per node
return [] if root is None else ([root.val]
+ [y for child in root.children for y in self.preorderTraversal(child)])

Answer 2

它可以这样工作：

class Solution:
def preorder(self, root):
return [] if root is None else [root.val] + [value 
for child in (root.children or []) 
for value in self.preorder(child)]

其思想是，列表理解取代了对append的重复调用，而不是对extend的重复调用。映射到上述列表理解版本的非理解代码是：

class Solution:
def preorder(self, root):
if root is None:
return []
res = [root.val]
for child in (root.children or []):
for value in self.preorder(child):
res.append(value)
return res