二叉树后序遍历的非递归算法
时间: 2023-09-16 11:14:54 浏览: 53
二叉树的后序遍历非递归算法可以使用两个栈来实现,具体步骤如下:
1. 定义两个栈,stack1和stack2。
2. 将根节点压入stack1中。
3. 从stack1中弹出栈顶元素,将其压入stack2中。
4. 如果该节点有左子节点,则将其左子节点压入stack1中。
5. 如果该节点有右子节点,则将其右子节点压入stack1中。
6. 重复步骤3~5,直到stack1为空。
7. 弹出stack2中的元素,输出该元素的值。
8. 重复步骤7,直到stack2为空。
下面是Java代码实现:
```java
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
result.add(stack2.pop().val);
}
return result;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)