二叉树遍历的实现
二叉树（Binary Tree）指的是每个节点最多只有两个子节点的树结构，左子节点和右子节点分别称为左子树和右子树。对于二叉树的遍历就是指按照一定顺序，将树上的每个节点都访问一遍的操作。本文将从二叉树的先序遍历、中序遍历、后序遍历以及层次遍历四个方面来讲解二叉树的遍历实现。
1. 先序遍历
先序遍历是指从根节点开始，依次访问根节点、左子树、右子树的遍历。对于具有根节点的二叉树，先序遍历的代码实现可以使用递归和栈两种方式，其中递归是最常见的实现方式。递归实现代码如下：
```python
def preorder_traversal(root):
if root is None:
return []
result = [root.val]
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
```
栈实现代码如下：
```python
def preorder_traversal(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
```
2. 中序遍历
中序遍历是指从根节点开始，依次访问左子树、根节点、右子树的遍历。中序遍历同样可以使用递归和栈两种方式进行实现。递归实现的代码如下：
```python
def inorder_traversal(root):
if root is None:
return []
result = []
result += inorder_traversal(root.left)
result.append(root.val)
result += inorder_traversal(root.right)
return result
```
栈实现的代码如下：
```python
def inorder_traversal(root):
if root is None:
return []
result = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
result.append(root.val)
root = root.right
return result
```
3. 后序遍历
后序遍历是指从根节点开始，依次访问左子树、右子树、根节点的遍历。对于具有根节点的二叉树，后序遍历同样可以使用递归和栈两种方式进行实现。递归实现的代码如下：
```python
def postorder_traversal(root):
if root is None:
return []
result = []
result += postorder_traversal(root.left)
result += postorder_traversal(root.right)
result.append(root.val)
return result
```
栈实现的代码如下：
```python
def postorder_traversal(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
result.append(node.val)
return result[::-1]
```
4. 层次遍历
层次遍历是指按照树的层级顺序，逐层访问树节点的遍历。层次遍历可以使用队列来进行实现，代码如下：
```python
def levelorder_traversal(root):
if root is None:
return []
result = []
queue = [root]
while queue:
length = len(queue)
res = []
for _ in range(length):
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(res)
return result
```
