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

一般来说二叉树的先序遍历‌也称‌前序遍历‌是一种深度优先遍历方式其访问顺序遵循“‌根左右‌”原则即‌访问根节点‌‌递归地先序遍历左子树‌‌递归地先序遍历右子树‌。核心要点‌别名‌先根遍历、先序周游。‌时间复杂度‌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) # 将左子树入栈。