二叉树的深度优先遍历可以分为先序、中序、后序遍历,请说明先序、中序、后序是如何遍历一棵二叉树的,请举例一颗二叉树,并给出后序遍历非递归的思想与实现代码。
时间: 2023-10-23 22:19:55 浏览: 40
二叉树的深度优先遍历可以分为先序、中序、后序遍历:
- 先序遍历:先访问根节点,再依次递归访问左子树和右子树;
- 中序遍历:先递归访问左子树,再访问根节点,最后递归访问右子树;
- 后序遍历:先递归访问左子树,再递归访问右子树,最后访问根节点。
以如下二叉树为例:
```
3
/ \
1 4
/ \
2 5
```
则先序遍历为:`3 1 2 5 4`,中序遍历为:`2 1 5 3 4`,后序遍历为:`2 5 1 4 3`。
下面给出后序遍历的非递归实现思路和代码:
后序遍历非递归实现的思想是利用一个栈来模拟递归操作,具体步骤如下:
1. 将根节点入栈;
2. 循环执行以下操作,直到栈为空:
- 取出栈顶元素,判断它是否有左右子树;
- 如果没有左右子树,说明该节点是叶子节点,可以直接输出;
- 如果有左右子树,将该节点的左右子树按照“根右左”的顺序依次入栈;
3. 输出的顺序即为后序遍历结果。
代码如下:
```python
def postorderTraversal(root):
stack = []
output = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if not node.left and not node.right:
output.append(node.val)
else:
stack.append(node)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return output[::-1]
```
其中,`output`用于存储输出结果,`[::-1]`表示将列表反转,因为是“左右根”的顺序入栈,所以最后输出时需要反转一下。