用栈实现二叉树前中后序遍历
时间: 2023-07-07 12:33:13 浏览: 56
好的,我可以帮您解答关于栈实现二叉树前中后序遍历的问题。
二叉树的前序遍历、中序遍历和后序遍历都可以用栈来实现。其中,前序遍历的顺序是:根节点 -> 左子树 -> 右子树;中序遍历的顺序是:左子树 -> 根节点 -> 右子树;后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
我们可以先将根节点压入栈中,然后按照相应的顺序遍历其左右子树,并将其子节点压入栈中。当遍历到叶子节点时,将其弹出栈并继续遍历其兄弟节点。直到栈为空时,遍历结束。
下面是用栈实现二叉树前序遍历的代码:
```python
def pre_order(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
下面是用栈实现二叉树中序遍历的代码:
```python
def in_order(root):
if not root:
return []
stack, res = [], []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
res.append(node.val)
root = node.right
return res
```
下面是用栈实现二叉树后序遍历的代码:
```python
def post_order(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
```
希望我的回答对您有所帮助。