二叉树遍历典型例题

二叉树是一种数据结构，其中每个节点最多有两个子节点。在计算机科学中，经常使用二叉树来处理和管理数据。在这篇文章中，我们将重点介绍二叉树的遍历方式，包括前序遍历、中序遍历和后序遍历，并提供一些典型例题供读者参考。

前序遍历

前序遍历是一种深度优先遍历方式，它首先访问根节点，然后递归地访问左子树和右子树。例如，对于下面这个二叉树：

1

/ \

2 3

/ \ \

4 5 6

前序遍历输出的结果为1->2->4->5->3->6。在编写递归函数实现前序遍历时，需要注意以下几点：

1. 需要先访问当前节点，再递归访问左子树和右子树；

2. 递归终止条件为遇到空节点。

中序遍历

中序遍历也是一种深度优先遍历方式，它先访问左子树，然后访问根节点，再访问右子树。对于上面这个二叉树，中序遍历输出的结果为4->2->5->1->3->6。在编写递归函数实现中序遍历时，需要注意以下几点：

1. 需要先递归访问左子树，再访问当前节点和右子树；

2. 递归终止条件为遇到空节点。

后序遍历

后序遍历也是一种深度优先遍历方式，它先访问左子树，然后访问右子树，最后访问根节点。对于上面这个二叉树，后序遍历输出的结果为4->5->2->6->3->1。在编写递归函数实现后序遍历时，需要注意以下几点：

1. 需要先递归访问左子树和右子树，再访问当前节点；

2. 递归终止条件为遇到空节点。

典型例题分析

下面我们将介绍几个典型的二叉树遍历问题，供读者参考。

1. 二叉树的最大深度

问题描述：给定一个二叉树，找出其最大深度。

解决方法：使用递归方式遍历二叉树，以每个节点为根节点，计算其左子树和右子树的最大深度，返回较大的那个值，其中递归终止条件为遇到空节点。具体实现可以参考下面这段代码：

```python

def maxDepth(root: TreeNode) -> int:

if not root:

return 0

left_depth = maxDepth(root.left)

right_depth = maxDepth(root.right)

return max(left_depth, right_depth) + 1

```

2. 二叉树的层序遍历

问题描述：给定一个二叉树，返回其节点值的按层序遍历。

解决方法：使用队列保存每一层的节点，首先将根节点加入队列中，然后依次取出队列中的节点，记录其值并加入结果列表中，接着将其左节点和右节点加入队列中，循环此过程，直到队列为空。具体实现可以参考下面这段代码：

```python

def levelOrder(root: TreeNode) -> List[List[int]]:

if not root:

return []

res = []

q = [root]

while q:

level = []

for i in range(len(q)):

node = q.pop(0)

level.append(node.val)

if node.left:

q.append(node.left)

if node.right:

q.append(node.right)

res.append(level)

return res

```

3. 不同的二叉搜索树

问题描述：给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

解决方法：使用递归方式，以每个数字为根节点，在左子树中构造1~(i-1)的BST，在右子树中构造(i+1)~n的BST，然后将两个子树重组，最后返回所有可能的重组结果。其中空子树也算一种二叉搜索树。具体实现可以参考下面这段代码：

```python

def generateTrees(n: int) -> List[TreeNode]:

def helper(start, end):

if start > end:

return [None]

res = []

for i in range(start, end + 1):

left_tree = helper(start, i - 1)

right_tree = helper(i + 1, end)

for l in left_tree:

for r in right_tree:

node = TreeNode(i)

node.left = l

node.right = r

res.append(node)

return res

return helper(1, n)

```