二叉树的先序遍历的非递归实现

一般来说，二叉树的先序遍历‌（也称‌前序遍历‌）是一种深度优先遍历方式，其访问顺序遵循“‌根左右‌”原则，即：

‌访问根节点‌；
‌递归地先序遍历左子树‌；
‌递归地先序遍历右子树‌。

核心要点

• ‌别名‌：先根遍历、先序周游。
• ‌时间复杂度‌：O(n)，其中 n 为二叉树中节点个数。
• ‌空间复杂度‌：O(h)，其中 h 为树的高度（递归栈深度）。

非递归实现是利用了栈这一数据结构。其基本思路是：

1.将根节点入栈。

2.循环：

• 弹出栈顶节点。
• 访问当前节点。
• 如果当前节点有右子树，则将右子树入栈。（由于栈的先进后出性质，所以先将右子树入栈，后将左子树入栈，出栈的时候是左子树先出栈，右子树后出栈，符合先序遍历的顺序）
• 如果当前节点有左子树，则将左子树入栈。

def dfs_preorder_non_recursive(root): if root is None: return stack = [root] # 将根节点入栈。 while stack: node = stack.pop() # 弹出栈顶节点。 print(node.val) # 访问当前节点。 if node.right: stack.append(node.right) # 将右子树入栈。 if node.left: stack.append(node.left) # 将左子树入栈。