二叉树遍历的实现

二叉树（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

```