用栈实现二叉树的非递归后序遍历
时间: 2023-11-20 11:07:00 浏览: 112
用栈实现二叉树先序遍历的非递归算法实践题.doc
非递归后序遍历二叉树可以使用两个栈来实现。具体实现步骤如下:
1. 定义两个栈,stack1和stack2,其中stack1用于辅助存储节点,stack2用于存储后序遍历的结果。
2. 将根节点入栈stack1。
3. 只要stack1不为空,就进行以下操作:
- 从stack1弹出一个节点,并将其压入stack2中。
- 如果该节点有左子节点,则将其左子节点压入stack1中。
- 如果该节点有右子节点,则将其右子节点压入stack1中。
4. 当stack1为空时,遍历结束。此时stack2中存储的就是后序遍历的结果。
下面是使用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 []
stack1, stack2 = [root], []
while stack1:
node = stack1.pop()
stack2.append(node.val)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
return stack2[::-1]
```
其中,[::-1]表示将列表翻转。
阅读全文