二叉树后序遍历的非递归算法。
时间: 2023-06-27 15:02:35 浏览: 94
二叉树后序遍历的非递归算法可以通过使用栈来实现。具体步骤如下:
1. 创建一个栈,将根节点入栈。
2. 定义一个变量last_visit,用来记录上一次访问的节点。
3. 当栈不为空时,取出栈顶节点,如果该节点没有左右子节点或者左右子节点已经被访问过,则访问该节点,并将last_visit设置为该节点。
4. 否则,将该节点的右子节点和左子节点依次入栈,保证左子节点先入栈。
5. 当遍历到节点时,如果该节点的右子节点是上一次访问的节点,则说明该节点的左右子节点都已经访问完毕,可以访问该节点并将last_visit设置为该节点。
下面是一段Python代码实现:
```python
def postorderTraversal(root):
if not root:
return []
stack, res = [], []
last_visit = None
while stack or root:
if root:
stack.append(root)
root = root.left
else:
peek = stack[-1]
if peek.right and last_visit != peek.right:
root = peek.right
else:
res.append(peek.val)
last_visit = stack.pop()
return res
```
其中,root代表当前节点,stack是用来存储节点的栈,res是用来存储遍历结果的数组,last_visit是上一次访问的节点。
阅读全文
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)