编写二叉树的后序遍历的非递归算法
时间: 2024-01-23 10:42:46 浏览: 25
二叉树的后序遍历的非递归算法可以使用栈来实现。具体步骤如下:
1. 定义一个栈,用于存储遍历过程中的节点。
2. 将根节点入栈。
3. 定义一个指针p,指向根节点。
4. 当栈不为空时,执行以下操作:
a. 如果栈顶元素的右孩子和左孩子都已经被访问过或者栈顶元素没有孩子,则弹出栈顶元素,并将其值加入结果数组中。
b. 否则,将栈顶元素的右孩子和左孩子依次入栈,注意入栈顺序是右孩子先入栈,左孩子后入栈。
5. 遍历完成后,结果数组中存储的就是二叉树后序遍历的结果。
以下是非递归后序遍历的代码实现:
```python
def postorderTraversal(root):
if not root:
return []
stack, res = [root], []
p = root
while stack:
if (not p.left and not p.right) or (p.left in res and p.right in res):
node = stack.pop()
res.append(node.val)
p = node
else:
if p.right:
stack.append(p.right)
if p.left:
stack.append(p.left)
p = p.left if p.left else p.right
return res
```
其中,root为二叉树的根节点,stack为栈,res为结果数组,p为指针,val为节点的值。如果节点没有左右孩子或者左右孩子都已经被访问过,则将节点弹出栈并将其值加入结果数组中,否则将右孩子和左孩子入栈,并将指针p指向左孩子(如果左孩子为空则指向右孩子)。最终返回结果数组。