layout: post
title: "二叉树的N种遍历方法（Python）"
description: ""
categories: [DSA]
tags: [二叉树]
redirect_from:
- /2022/10/03/
二叉树描述
from __future__ import annotations
import collections
class Node:
def __init__(self, val: int) -> None:
self.val = val
self.left = None
self.right = None
深度优先搜索（DFS）
递归
递归的三种遍历
def preorder(tree: Node | None) -> list[int]:
return [] if not tree else [tree.val] + preorder(tree.left) + preorder(tree.right)
def inorder(tree: Node | None) -> list[int]:
return [] if not tree else inorder(tree.left) + [tree.val] + inorder(tree.right)
def postorder(tree: Node | None) -> list[int]:
return [] if not tree else postorder(tree.left) + postorder(tree.right) + [tree.val]
二叉树的序列化
# convert2Str:
# ^1#^2#^4#$$^5#^6#$$$^3#^7#^8#$^9#$$$$
# preorder:
# [1, 2, 4, 5, 6, 3, 7, 8, 9]
def convert2Str(p: Node) -> str:
return "^" + str(p.val) + "#" + convert2Str(p.left) + convert2Str(p.right) if p else "$"
def is_subtree(root: Node, subRoot: Node) -> bool:
def convert(p):
return "^" + str(p.val) + "#" + convert(p.left) + convert(p.right) if p else "$"
return convert(subRoot) in convert(root)
非递归
非递归的三种遍历
# *非递归先根遍历(入栈时访问)
# *步骤一：从根节点开始，如果左孩子存在，则访问左孩子并将其入栈。重复直到左孩子不存在
# *步骤二：依次出栈，并将出栈结点的右孩子赋值给根节点，重复步骤一。
def preorder_stack(tree: Node | None) -> list[int]:
stack = []
ret = []
cur = tree
while True:
while cur:
# 入栈时遍历
ret.append(cur.val)
stack.append(cur)
cur = cur.left
if not stack:
break
next = stack.pop()
cur = next.right
return ret
# *非递归中根遍历（出栈时访问）
# *步骤一：从根节点开始，如果左孩子存在，则入栈左孩子。重复直到左孩子不存在。
# *步骤二：依次出栈，并访问栈顶元素。将栈顶结点的右结点赋值给根节点，重复步骤一。
def inorder_stack(tree: Node | None) -> list[int]:
stack = []
ret = []
cur = tree
while True:
while cur:
stack.append(cur)
cur = cur.left
if not stack:
break
next = stack.pop()
# 出栈时遍历
ret.append(next.val)
cur = next.right
return ret
# *非递归后根遍历（类似中根遍历+标记位）
# *步骤一：从根节点开始，如果左孩子存在，则入栈左孩子。重复直到左孩子不存在。
# *步骤二：依次出栈。如果出栈结点p的右孩子为空或者已经访问过，访问p。否则将p的右孩子赋值给根节点，重复步骤一。
def postorder_stack(tree: Node | None) -> list[int]:
stack = []
ret = []
cur = tree
tmp = None # 标记刚刚访问过的节点
while True:
while cur:
stack.append(cur)
cur = cur.left
if not stack:
break
next = stack[-1]
# 右孩子为空，或者右孩子被访问过，则访问该节点并pop
if not next.right or next.right == tmp:
tmp = next
ret.append(next.val)
stack.pop()
else:
cur = next.right
return ret
另一种非递归遍历
# 先把根节点入栈
# 出栈并访问
# 如果有右节点，则先把右节点入栈；如果有左节点，再把左节点入栈；
# 回到第二步循环，直到栈空。
def preorder_stack2(tree: Node | None) -> list[int]:
if not tree:
return []
stack = [tree]
ret = []
while stack:
x = stack.pop()
ret.append(x.val)
if x.right:
stack.append(x.right)
if x.left:
stack.append(x.left)
return ret
# 先把根节点入栈
# 出栈并访问
# 如果有左节点，则先把左节点入栈；如果有右节点，再把右节点入栈；
# 回到第二步循环，直到栈空。倒序输出。
def postorder_stack2(tree: Node | None) -> list[int]:
if not tree:
return []
stack = [tree]
ret = []
while stack:
x = stack.pop()
ret.append(x.val)
if x.left:
stack.append(x.left)
if x.right:
stack.append(x.right)
return ret[::-1]
广度优先搜索（BFS）
层次遍历
简单层次遍历
# 根节点入队
# 出队并访问，如果有左右节点，则左右节点依次入队
# 重复上一步直到队列为空
def level_order(tree: Node | None) -> list[int]:
if not tree:
return []
q = collections.deque([tree])
ret = []
while q:
cur = q.popleft()
ret.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return ret
分组层次遍历
def level_order2(tree: Node | None) -> list[list[int]]:
if not tree:
return []
level = [tree]
ret = []
while level:
level_vals = []
next_level = []
for v in level:
level_vals.append(v.val)
if v.left:
next_level.append(v.left)
if v.right:
next_level.append(v.right)
level = next_level
ret.append(level_vals)
return ret
「夹带私货」层次遍历
def root2leaf_path(tree: Node | None) -> list[str]:
if not tree:
return []
q = collections.deque([(tree, str(tree.val))])
ret = []
while q:
cur_node, cur_path = q.popleft()
# ret.append(cur.val)
if cur_node.left:
q.append((cur_node.left, cur_path + "-" + str(cur_node.left.val)))
if cur_node.right:
q.append((cur_node.right, cur_path + "-" + str(cur_node.right.val)))
if not cur_node.left and not cur_node.right:
ret.append(cur_path)
return ret
树状打印
从左到右树状打印
# 从左往右打印一棵树
def tree_print(root: Node, level: int):
if not root:
return
tree_print(root.right, level + 1)
for i in range(level):
print(" ", end=" ")
print(root.val)
tree_print(root.left, level + 1)
从上到下树状打印
# 从上到下 ，"树"状打印一颗二叉树
def print_tree(tree: Node) -> list[list[int]]:
rows = height(tree)
cols = 2 ** rows - 1
res = [['' for _ in range(cols)] for _ in range(rows)]
def traverse(node, level, pos):
if not node:
return
left_padding, spacing = 2 ** (rows - level - 1) - 1, 2 ** (rows - level) - 1
index = left_padding + pos * (spacing + 1)
res[level][index] = str(node.val)
traverse(node.left, level + 1, pos << 1)
traverse(node.right, level + 1, (pos << 1) + 1)
traverse(tree, 0, 0)
## print
for v in res:
for vv in v:
if vv == "":
print(' ', end="")
else:
print(vv, end="")
print()
return res
