二叉树后序遍历的非递归算法
时间: 2023-06-18 11:03:29 浏览: 58
二叉树后序遍历的非递归算法可以使用栈来实现。具体步骤如下:
1. 定义一个栈和一个指针p,初始时p指向根节点。
2. 将p节点及其左子树依次入栈,直到p为空。
3. 弹出栈顶节点,如果该节点没有右子树或者右子树已经被访问过了,则访问该节点并将其标记为已访问。
4. 如果该节点有右子树且右子树未被访问,则将p指向右子树,并将该节点重新入栈。
5. 重复步骤3、4直到栈为空。
下面是该算法的Python实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def postorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [(root, False)]
while stack:
curr, visited = stack.pop()
if visited:
res.append(curr.val)
else:
stack.append((curr, True))
if curr.right:
stack.append((curr.right, False))
if curr.left:
stack.append((curr.left, False))
return res
```
其中,stack中存放的是一个元组,元组的第一个元素是节点,第二个元素是一个布尔值,表示该节点是否已经被访问过了。在访问一个节点时,先判断该节点是否已经被访问过了,如果已经被访问过,则将其值加入结果列表中;否则,将该节点和False入栈,并将其右子树和左子树依次入栈。这样可以保证在访问一个节点之前,其左右子树已经被访问过了。