【前序、中序、后序遍历递归栈的实现】

特性	DFS（深度优先搜索）	BFS（广度优先搜索）
遍历顺序	深度优先，沿着树的深度遍历，直到叶子节点再回溯。	广度优先，按层次从上到下、从左到右遍历。
实现方式	递归或栈	队列
空间复杂度	O(h)，h 为树的高度（递归栈的深度）。	O(w)，w 为树的最大宽度（队列的大小）。
时间复杂度	O(n)，n 为树的节点数。	O(n)，n 为树的节点数。
遍历结果示例	前序：1 2 4 5 3 6 中序：4 2 5 1 3 6 后序：4 5 2 6 3 1	层序：1 2 3 4 5 6

  		1/ \2   3/ \   \4   5   6

递归实现

前序遍历

根节点 -> 左子树 -> 右子树

def pre_order_traversal(root):if root is None:returnprint(root.val)  # 访问根节点pre_order_traversal(root.left)  # 递归遍历左子树pre_order_traversal(root.right)  # 递归遍历右子树

中序遍历

左子树 -> 根节点 -> 右子树

def in_order_traversal(root):if root is None:returnin_order_traversal(root.left)  # 递归遍历左子树print(root.val)  # 访问根节点in_order_traversal(root.right)  # 递归遍历右子树

后序遍历

左子树 -> 右子树 -> 根节点

def post_order_traversal(root):if root is None:returnpost_order_traversal(root.left)  # 递归遍历左子树post_order_traversal(root.right)  # 递归遍历右子树print(root.val)  # 访问根节点

栈实现

前序遍历

前序遍历的顺序是：根-> 左 -> 右 (由上往下)
栈：根压入；根弹出；右、左压入；左、右弹出；
弹出顺序为：根-> 左 -> 右

def preorder_traversal(root):if not root:return []stack, result = [root], []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

中序遍历

前序遍历的顺序是：左 -> 根-> 右 (由下往上)
栈：最左的根压入；根弹出；右压入；右弹出； (最左的根:既是左，又是根)
弹出顺序为：左 -> 根-> 右

      1/ \2   3\4(1)1/ \2   3(2)

def inorder_traversal(root):stack, result = [], []current = rootwhile current or stack:# 先遍历到最左节点while current:stack.append(current)current = current.left# 弹出栈顶元素并访问current = stack.pop()result.append(current.val)# 遍历右子树current = current.rightreturn result

后序遍历

前序遍历的顺序是：左 -> 右 -> 根 (由下往上)
栈：根压入；根弹出；左、右、压入；右、左弹出；
弹出顺序为：根 -> 右 -> 左 所以需要在反转

def postorder_traversal(root):if not root:return []stack, result = [root], []while stack:node = stack.pop()result.append(node.val)# 先压左子树，再压右子树，保证右子树先出栈if node.left:stack.append(node.left)if node.right:stack.append(node.right)# 最后反转结果，得到后序遍历return result[::-1]