树 (Tree)

binary treetreeLeetCodealgorithminterview

树 (Tree)

树是一种分层的数据结构，由节点和边组成，是最常用的非线性数据结构之一。

基础概念

树的类型

  1. 普通二叉树
       1
     /   \
    2     3
   / \   / \
  4   5 6   7
  1. 二叉搜索树（BST）
       4
     /   \
    2     6
   / \   / \
  1   3 5   7
  1. 平衡二叉树（AVL）
    3
   / \
  2   4
 /     \
1       5
  1. 完全二叉树
       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'))

常见技巧

  1. 递归是处理树问题的核心方法
  2. 使用辅助函数传递额外参数
  3. 考虑空节点和边界情况
  4. 画图帮助理解遍历过程
  5. 灵活运用前中后序遍历

相关题目