试着写一个二叉树后序遍历的非递归算法。
时间: 2023-06-16 09:05:54 浏览: 55
二叉树的后序遍历顺序是先遍历左子树,再遍历右子树,最后遍历根节点。非递归算法通常使用栈来实现。
算法步骤如下:
1. 创建一个栈,用来存储待遍历的节点。
2. 将根节点压入栈中,然后进入循环。
3. 每次循环,从栈中弹出一个节点。
4. 如果该节点没有左右子节点,或者其左右子节点都已经被访问过了,就输出该节点的值,并继续弹出栈顶元素。
5. 如果该节点有左右子节点,就先将右子节点压入栈中,再将左子节点压入栈中。这样可以保证在访问该节点时,其左右子节点都已经被访问过了。
6. 重复步骤3到步骤5,直到栈为空。
下面是使用 Python 语言实现的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def postorderTraversal(root):
if not root:
return []
stack, res = [(root, False)], []
while stack:
node, visited = stack.pop()
if visited:
res.append(node.val)
else:
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return res
```
这个算法的时间复杂度是 O(n),空间复杂度也是 O(n),其中 n 是二叉树的节点数。