python非递归后序遍历
时间: 2023-07-02 17:16:34 浏览: 43
非递归后序遍历可以使用两个栈来实现,具体步骤如下:
1. 定义两个栈 stack1 和 stack2,将根节点压入 stack1 中。
2. 从 stack1 中弹出栈顶元素,然后将其压入 stack2 中。
3. 分别将该节点的左子节点和右子节点压入 stack1 中(如果存在的话)。
4. 重复步骤2和3,直到 stack1 为空。
5. 从 stack2 中依次弹出元素并输出,即为后序遍历的结果。
下面是 Python 代码实现:
```python
def postorderTraversal(root):
if not root:
return []
stack1, stack2 = [root], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
res = []
while stack2:
res.append(stack2.pop().val)
return res
```
其中,root 表示树的根节点,val 表示节点的值。
相关问题
用栈实现二叉树的非递归后序遍历
非递归后序遍历二叉树可以使用两个栈来实现。具体实现步骤如下:
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]表示将列表翻转。
二叉树后序遍历非递归算法
二叉树后序遍历的非递归算法可以使用两个栈来实现。具体步骤如下:
1. 定义两个栈stack1和stack2,用于存放节点。
2. 将根节点压入stack1中。
3. 循环执行以下操作,直到stack1为空:
1. 从stack1中弹出一个节点p,并将其压入stack2中。
2. 将p的左子节点压入stack1中。
3. 将p的右子节点压入stack1中。
4. 循环执行以下操作,直到stack2为空:
1. 从stack2中弹出一个节点p,并输出p的值。
这种算法的思路是,先按照根节点、右子节点、左子节点的顺序遍历二叉树,并将遍历的结果压入stack2中。最后从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)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
res = []
while stack2:
res.append(stack2.pop().val)
return res
```
这个算法的时间复杂度和空间复杂度都是O(n),其中n是二叉树的节点数。