树 (Tree)
树 (Tree)
树是一种分层的数据结构,由节点和边组成,是最常用的非线性数据结构之一。
基础概念
树的类型
- 普通二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
- 二叉搜索树(BST)
4
/ \
2 6
/ \ / \
1 3 5 7
- 平衡二叉树(AVL)
3
/ \
2 4
/ \
1 5
- 完全二叉树
1
/ \
2 3
/ \ /
4 5 6
基本操作
- 遍历:前序、中序、后序、层序
- 插入:添加新节点
- 删除:移除指定节点
- 查找:搜索特定值
- 平衡:维护树的平衡性
- 旋转:调整树的结构
应用场景
- 表达式解析
- 文件系统
- 数据库索引
- 自动补全
- 区间查询
经典问题
1. 二叉树的前序遍历
LeetCode 144 - Binary Tree Preorder Traversal
遍历过程示意:
1
/ \
2 3
/ \
4 5
前序遍历路径: 1 -> 2 -> 4 -> 5 -> 3
def preorderTraversal(root):
res = []
def dfs(node):
if not node: return
res.append(node.val) # 访问根节点
dfs(node.left) # 遍历左子树
dfs(node.right) # 遍历右子树
dfs(root)
return res
2. 二叉树的最大深度
LeetCode 104 - Maximum Depth of Binary Tree
深度计算示意:
1 (深度=3)
/ \
2 3 (深度=2)
/ \
4 5 (深度=1)
def maxDepth(root):
if not root: return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
3. 最近公共祖先
LeetCode 236 - Lowest Common Ancestor of a Binary Tree
查找过程示意:
3 (LCA)
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
查找节点5和1的LCA:
1. 从根节点3开始
2. 在左子树找到5
3. 在右子树找到1
4. 节点3即为LCA
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
4. 验证二叉搜索树
LeetCode 98 - Validate Binary Search Tree
BST性质示意:
5
/ \
3 7
/ \ / \
2 4 6 8
对每个节点:
- 左子树的所有节点 < 当前节点
- 右子树的所有节点 > 当前节点
def isValidBST(root):
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return validate(node.left, min_val, node.val) and \
validate(node.right, node.val, max_val)
return validate(root, float('-inf'), float('inf'))
常见技巧
- 递归是处理树问题的核心方法
- 使用辅助函数传递额外参数
- 考虑空节点和边界情况
- 画图帮助理解遍历过程
- 灵活运用前中后序遍历
相关题目
- LeetCode 94 - Binary Tree Inorder Traversal
- LeetCode 102 - Binary Tree Level Order Traversal
- LeetCode 124 - Binary Tree Maximum Path Sum
- LeetCode 226 - Invert Binary Tree
- LeetCode 543 - Diameter of Binary Tree