二叉树遍历：LeetCode实战指南
二叉树是数据结构中的一种，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。二叉树在计算机科学中有着广泛的应用，如排序、搜索、路径查找等。在LeetCode等编程竞赛平台上，二叉树的遍历问题经常出现。本文将围绕二叉树的前序遍历、中序遍历、后序遍历以及层次遍历，结合LeetCode实战案例，进行详细讲解。
前序遍历
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。在LeetCode中，前序遍历的典型题目是“二叉树的遍历”（LeetCode 144）。
示例代码
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root):
if not root:
return []
return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
LeetCode实战案例
题目描述：给定一个二叉树，返回它的前序遍历。
输入：`[1,2,3,4,5,6,7]`
输出：`[1,2,4,5,3,6,7]`
中序遍历
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。在LeetCode中，中序遍历的典型题目是“二叉搜索树的中序遍历”（LeetCode 94）。
示例代码
python
def inorderTraversal(root):
if not root:
return []
return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
LeetCode实战案例
题目描述：给定一个二叉树，返回它的中序遍历。
输入：`[1,2,3,4,5,6,7]`
输出：`[4,2,5,1,6,3,7]`
后序遍历
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。在LeetCode中，后序遍历的典型题目是“二叉树的后序遍历”（LeetCode 145）。
示例代码
python
def postorderTraversal(root):
if not root:
return []
return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]
LeetCode实战案例
题目描述：给定一个二叉树，返回它的后序遍历。
输入：`[1,2,3,4,5,6,7]`
输出：`[4,5,2,6,7,3,1]`
层次遍历
层次遍历的顺序是：从上到下，从左到右。在LeetCode中，层次遍历的典型题目是“二叉树的层次遍历”（LeetCode 102）。
示例代码
python
from collections import deque
def levelOrder(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
LeetCode实战案例
题目描述：给定一个二叉树，返回它的层次遍历。
输入：`[1,2,3,4,5,6,7]`
输出：`[[1],[2,3],[4,5,6,7]]`
总结
本文介绍了二叉树的前序遍历、中序遍历、后序遍历以及层次遍历，并结合LeetCode实战案例进行了详细讲解。通过学习这些遍历方法，我们可以更好地理解二叉树的结构和性质，为解决更多与二叉树相关的问题打下基础。在实际编程中，熟练掌握这些遍历方法将有助于提高代码质量和效率。
Comments NOTHING