树

本章目标：掌握二叉树的各种遍历方式与经典递归模式，能解决 BST 和路径类问题。

你将学到

• 二叉树四种遍历（前序、中序、后序、层序）
• 递归与迭代两种写法
• BST 的性质与验证
• 最近公共祖先（LCA）
• 路径总和系列
• 平衡二叉树判断
• 序列化与反序列化

1. 概念

树是递归定义的数据结构：一棵树要么为空，要么由根节点和若干子树组成。二叉树每个节点最多有两个子节点。

树的绝大多数问题都可以用递归解决：把问题分解为「左子树的结果 + 右子树的结果 + 当前节点的处理」。掌握树的关键在于写出正确的递归函数，定义清楚「这个函数返回什么」。

二叉搜索树（BST）的特殊性质：中序遍历得到递增序列。这一性质在验证 BST、找前驱后继、第 K 小等问题中反复使用。

2. 核心模板

二叉树定义

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) { self.val = val }
}

中序遍历（迭代）

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []
    var stack: [TreeNode] = []
    var curr = root
    while curr != nil || !stack.isEmpty {
        while let node = curr {
            stack.append(node)
            curr = node.left
        }
        curr = stack.removeLast()
        result.append(curr!.val)
        curr = curr!.right
    }
    return result
}

层序遍历（BFS）

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }
    var result: [[Int]] = []
    var queue: [TreeNode] = [root]
    while !queue.isEmpty {
        let count = queue.count
        var level: [Int] = []
        for _ in 0..<count {
            let node = queue.removeFirst()
            level.append(node.val)
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }
        result.append(level)
    }
    return result
}

复杂度

• 所有遍历：时间 O(n)，空间 O(h)，h 为树高，最坏 O(n)

3. 经典题目精讲

LeetCode 104 · 二叉树最大深度

题意：求二叉树最大深度。

思路：经典递归——当前深度 = 1 + max(左子树深度, 右子树深度)。

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
}

LeetCode 236 · 最近公共祖先

题意：找两个节点 p 和 q 在二叉树中的最近公共祖先。

思路：递归——如果当前节点是 p 或 q，返回它；左右子树各找一次，两边都找到说明当前节点就是 LCA。

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    if root === p || root === q { return root }
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if left != nil && right != nil { return root }
    return left ?? right
}

LeetCode 110 · 平衡二叉树

题意：判断二叉树是否高度平衡（左右子树高度差不超过 1）。

思路：自底向上返回高度，遇到不平衡直接返回 -1 提前终止。

func isBalanced(_ root: TreeNode?) -> Bool {
    return height(root) != -1
}

private func height(_ node: TreeNode?) -> Int {
    guard let node = node else { return 0 }
    let leftH = height(node.left)
    if leftH == -1 { return -1 }
    let rightH = height(node.right)
    if rightH == -1 { return -1 }
    if abs(leftH - rightH) > 1 { return -1 }
    return 1 + max(leftH, rightH)
}

4. 易错点

• ⚠️ 递归基线（base case）别忘了处理 nil
• ⚠️ 验证 BST 时不能只比较节点与其直接子节点，需传递上下界
• ⚠️ Swift 中树节点是引用类型，=== 比较身份
• ⚠️ 层序遍历记录每层数量后再统一出队，否则层数混乱

5. 推荐刷题清单

题号	题名	难度	关键
94	中序遍历	Easy	迭代遍历
102	层序遍历	Medium	BFS
104	二叉树最大深度	Easy	递归
110	平衡二叉树	Easy	自底向上
226	翻转二叉树	Easy	递归交换
236	最近公共祖先	Medium	递归
297	序列化二叉树	Hard	前序/层序

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 12 章