二叉树遍历
二叉树是一种树形数据结构，其特点是每个节点最多有两个子节点（分别称为左子节点和右子节点），子树的左右顺序不能颠倒（即左子树和右子树是有区别的）。
基本定义
- 二叉树由节点和边组成，每个节点包含一个值（数据）和两个指针（分别指向左子节点和右子节点）。
- 没有子节点的节点称为叶子节点（左、右子节点均为
None）。 - 只有一个根节点（无父节点）的二叉树称为空树（根节点为
None）。 - 节点的度：该节点拥有的子节点数量（二叉树中节点的度只能是 0、1、2）。
1. 节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val # 节点值
self.left = left # 左子节点
self.right = right # 右子节点
2. 前序遍历
1. 循环实现
def preorder_iterative(root):
"""前序遍历（迭代）：根 -> 左 -> 右"""
if not root:
return []
stack = [root] # 栈初始化，先放入根节点
result = []
while stack:
node = stack.pop() # 弹出栈顶节点（先处理根）
result.append(node.val)
# 注意：栈是后进先出，需先放右子树，再放左子树（保证左子树先被处理）
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
2. 标记实现
将未访问节点标记为白色(0)，访问过的节点标记为灰色(1)
def preorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)] # 初始栈：未访问的根节点
while stack:
color, node = stack.pop()
if node is None:
continue # 空节点跳过
if color == WHITE:
# 按右 → 左 → 根的顺序入栈（栈后进先出，保证根先处理）
stack.append((WHITE, node.right)) # 右子树后处理，先入栈
stack.append((WHITE, node.left)) # 左子树中间处理，后入栈
stack.append((GRAY, node)) # 根节点先处理，最后入栈
else:
# 已访问（GRAY）的节点，直接记录值
res.append(node.val)
return res
3. 递归实现
def preorder_recursive(root):
"""前序遍历（递归）：根 -> 左 -> 右"""
if not root: # 空节点返回空列表
return []
# 先添加根节点值，再递归左子树，最后递归右子树
return [root.val] + preorder_recursive(root.left) + preorder_recursive(root.right)
3. 中序遍历
1.循环实现
def inorder_iterative(root):
"""中序遍历（迭代）：左 -> 根 -> 右"""
if not root:
return []
stack = []
result = []
current = root # 指针记录当前节点
while current or stack:
# 先遍历到最左子节点（左子树优先）
while current:
stack.append(current)
current = current.left
# 弹出最左节点（处理根）
current = stack.pop()
result.append(current.val)
# 转向右子树（处理右）
current = current.right
return result
2. 标记实现
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
3. 递归实现
def inorder_recursive(root):
"""中序遍历（递归）：左 -> 根 -> 右"""
if not root:
return []
# 先递归左子树，再添加根节点值，最后递归右子树
return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)
4. 后序遍历
1.循环实现
def postorder_iterative(root):
"""后序遍历（迭代）：左 -> 右 -> 根"""
if not root:
return []
stack = []
result = []
prev = None # 记录上一个访问的节点
current = root
while current or stack:
# 先遍历到最左子节点
while current:
stack.append(current)
current = current.left
current = stack[-1] # 查看栈顶节点（未访问）
# 若右子树为空或已访问，则处理当前节点（根）
if not current.right or current.right == prev:
result.append(current.val)
stack.pop()
prev = current # 标记当前节点为已访问
current = None # 继续处理栈顶
else:
# 否则先处理右子树
current = current.right
return result
2. 标记实现
def postorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)] # 初始栈：未访问的根节点
while stack:
color, node = stack.pop()
if node is None:
continue # 空节点跳过
if color == WHITE:
# 按根 → 右 → 左的顺序入栈（栈后进先出，保证左→右→根的顺序）
stack.append((GRAY, node)) # 根节点最后处理，先入栈
stack.append((WHITE, node.right)) # 右子树中间处理，后入栈
stack.append((WHITE, node.left)) # 左子树先处理，最后入栈
else:
# 已访问（GRAY）的节点，直接记录值
res.append(node.val)
return res
3. 递归实现
def postorder_recursive(root):
"""后序遍历（递归）：左 -> 右 -> 根"""
if not root:
return []
# 先递归左子树，再递归右子树，最后添加根节点值
return postorder_recursive(root.left) + postorder_recursive(root.right) + [root.val]
发表评论