48 lines
1.0 KiB
Python
48 lines
1.0 KiB
Python
|
from .binary_tree import TreeNode
|
|||
|
|
|
|||
|
|
"""
|
|||
|
|
二叉树的遍历：层序遍历，一层一层的遍历，方向为从左到右或从右到左
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def level_order(root: TreeNode):
|
|||
|
|
q = [root]
|
|||
|
|
res = []
|
|||
|
|
while q:
|
|||
|
|
node = q.pop(0)
|
|||
|
|
res.append(node.val)
|
|||
|
|
if node.left:
|
|||
|
|
q.append(node.left)
|
|||
|
|
if node.right:
|
|||
|
|
q.append(node.right)
|
|||
|
|
return res
|
|||
|
|
|
|||
|
|
|
|||
|
|
"""
|
|||
|
|
二叉树遍历：前序、中序、后序遍历，都属于「深度优先遍历 depth-first traversal, DFS」
|
|||
|
|
|
|||
|
|
前序：先遍历根节点，再遍历左节点，再遍历右节点
|
|||
|
|
中续：先遍历左节点，再遍历根节点，再遍历右节点
|
|||
|
|
后续：先左，再右，后中
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def pre_order(root: TreeNode):
|
|||
|
|
# 前序遍历
|
|||
|
|
print(root.val)
|
|||
|
|
if root.left:
|
|||
|
|
pre_order(root.left)
|
|||
|
|
if root.right:
|
|||
|
|
pre_order(root.right)
|
|||
|
|
|
|||
|
|
|
|||
|
|
def in_order(root: TreeNode):
|
|||
|
|
in_order(root.left)
|
|||
|
|
print(root.val)
|
|||
|
|
in_order(root.right)
|
|||
|
|
|
|||
|
|
|
|||
|
|
def post_order(root: TreeNode):
|
|||
|
|
post_order(root.left)
|
|||
|
|
post_order(root.right)
|
|||
|
|
print(root.val)
|