第六章树与二叉树¶

树是一种重要的非线性数据结构，广泛应用于文件系统、数据库索引、编译器语法分析等领域。本章从基本概念出发，讲解二叉树的各种操作与技巧。

6.1 树的基本概念¶

6.1.1 定义¶

树是由 n（n >= 0）个节点组成的有限集合：

当 n = 0 时，为空树
当 n > 0 时，有且仅有一个根节点（Root），其余节点可分为若干个互不相交的子集，每个子集本身又是一棵树，称为根的子树

graph TD
    A["1 (根节点)"] --> B["2"]
    A --> C["3"]
    A --> D["4"]
    B --> E["5"]
    B --> F["6"]
    D --> G["7"]

6.1.2 核心术语¶

术语	定义	示例（上图）
节点（Node）	树中的每个元素	1, 2, 3, ...
根（Root）	没有父节点的节点	1
叶子（Leaf）	没有子节点的节点	5, 6, 3, 7
边（Edge）	连接父子节点的线	(1,2), (1,3), ...
度（Degree）	节点的子节点个数	节点1的度为3
层（Level）	根为第 1 层，子节点比父节点深一层	节点5在第3层
深度（Depth）	节点所在的层数（根的深度为 1）	节点5的深度为3
高度（Height）	树中节点的最大层数（最深叶子所在层数）	树的高度为3
子孙（Descendant）	节点的所有后代	节点1的子孙：2,3,4,5,6,7
祖先（Ancestor）	到根路径上的所有节点	节点5的祖先：2,1
森林（Forest）	若干棵互不相交的树的集合	去掉根后的子树们

深度/高度的两种口径

有些教材按边数定义深度和高度（根的深度为 0）。本书统一采用层数口径：根为第 1 层，深度 = 节点所在层数，高度 = 最大层数。这样后文"深度为 h 的满二叉树有 2^h - 1 个节点"、"完全二叉树的高度 h = floor(log2 n) + 1" 等公式才能直接成立。LeetCode 题面（如 104 题最大深度按节点数计）也采用这一口径。

6.1.3 树的存储方式¶

在竞赛中，树常用以下方式存储：

1. 邻接表（最常用）

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;

vector<int> adj[MAXN];  // 邻接表，adj[i] 存储节点 i 的所有邻居

// 添加一条 u-v 的边（无向树）
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

邻接表在一般树（非二叉树）上如何配合 DFS 使用，见本章 6.9 一般树上的 DFS 与树形 DP 初步。

2. 父节点数组

const int MAXN = 100010;
int parent[MAXN];  // parent[i] 表示节点 i 的父节点
// 根节点的 parent 为 -1

3. 左孩子右兄弟表示法

const int MAXN = 100010;
int leftChild[MAXN];   // 第一个子节点
int rightSibling[MAXN]; // 右兄弟节点

6.2 二叉树基础¶

6.2.1 定义¶

二叉树是每个节点最多有两个子节点的树，分别称为左子节点和右子节点。

graph TD
    A["1"] --> B["2 (左子)"]
    A --> C["3 (右子)"]
    B --> D["4"]
    B --> E["5"]
    C --> F["∅ (左空)"]
    C --> G["6"]

6.2.2 特殊的二叉树¶

满二叉树：每一层的节点数都达到最大值。

graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["7"]

深度为 h 的满二叉树有 2^h - 1 个节点。

完全二叉树：除了最后一层外，每一层都是满的，且最后一层的节点从左到右连续排列。

graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]

完全二叉树的重要性质：

若节点从 1 开始编号，则节点 i 的左子节点为 2i，右子节点为 2i + 1，父节点为 i / 2
这就是堆用数组存储的理论基础

6.2.3 二叉树的性质¶

性质	公式
第 i 层最多有	2^(i-1) 个节点
深度为 h 的二叉树最多有	2^h - 1 个节点
叶子节点数 n0 和度为 2 的节点数 n2 的关系	n0 = n2 + 1
完全二叉树的高度	h = floor(log2(n)) + 1

6.2.4 二叉树的存储¶

// 方式一：链式存储（最常用）
struct TreeNode {
    int val;              // 节点值
    TreeNode* left;       // 左子节点
    TreeNode* right;      // 右子节点
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 方式二：数组存储（适用于完全二叉树）
// 节点 i 的左子为 2i，右子为 2i+1，父为 i/2
const int MAXN = 100010;
int tree[MAXN];

6.3 二叉树遍历¶

6.3.1 三种深度优先遍历¶

graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["7"]

遍历方式	顺序	结果
前序遍历（Preorder）	根 → 左 → 右	1, 2, 4, 5, 3, 6, 7
中序遍历（Inorder）	左 → 根 → 右	4, 2, 5, 1, 6, 3, 7
后序遍历（Postorder）	左 → 右 → 根	4, 5, 2, 6, 7, 3, 1

6.3.2 递归实现¶

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

vector<int> res;

// 前序遍历：根 → 左 → 右
void preorder(TreeNode* root) {
    if (root == nullptr) return;  // 空节点直接返回
    res.push_back(root->val);     // 访问根节点
    preorder(root->left);         // 递归遍历左子树
    preorder(root->right);        // 递归遍历右子树
}

// 中序遍历：左 → 根 → 右
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    res.push_back(root->val);
    inorder(root->right);
}

// 后序遍历：左 → 右 → 根
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    res.push_back(root->val);
}

6.3.3 迭代实现（用栈模拟递归）¶

递归的本质是系统调用栈，迭代版用显式的栈来模拟。

前序遍历的迭代实现：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 前序遍历迭代版
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;

    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);  // 访问当前节点

        // 注意：先压右子节点，再压左子节点（栈是后进先出）
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return res;
}

中序遍历的迭代实现：

// 中序遍历迭代版
// 核心思想：一直往左走，不能走时访问节点，再转向右子树
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;

    while (cur != nullptr || !st.empty()) {
        // 一直往左走，将沿途节点压栈
        while (cur != nullptr) {
            st.push(cur);
            cur = cur->left;
        }
        // 到达最左边，弹出栈顶并访问
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        // 转向右子树
        cur = cur->right;
    }
    return res;
}

后序遍历的迭代实现：

#include <algorithm>  // reverse 需要包含此头文件

// 后序遍历迭代版
// 技巧：前序是 根→左→右，改为 根→右→左，再反转即得到 左→右→根（后序）
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;

    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);

        // 先压左，再压右（与前序相反）
        if (node->left) st.push(node->left);
        if (node->right) st.push(node->right);
    }

    reverse(res.begin(), res.end());  // 反转得到后序
    return res;
}

6.3.4 层序遍历（BFS）¶

层序遍历使用队列，按层从上到下、从左到右访问每个节点。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 层序遍历，返回每一层的节点值
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (root == nullptr) return res;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数
        vector<int> level;

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        res.push_back(level);
    }
    return res;
}

时间复杂度： O(n)，每个节点恰好访问一次。

遍历的应用

前序遍历：序列化二叉树、复制树
中序遍历：BST 中得到有序序列
后序遍历：计算树的高度、释放内存
层序遍历：按层处理、求树的宽度

6.4 二叉搜索树（BST）¶

6.4.1 定义¶

二叉搜索树满足以下性质：

左子树中所有节点的值 < 根节点的值
右子树中所有节点的值 > 根节点的值
左右子树也分别是二叉搜索树

因此，BST 的中序遍历结果是有序的。

graph TD
    A["8"] --> B["3"]
    A --> C["10"]
    B --> D["1"]
    B --> E["6"]
    C --> F["∅"]
    C --> G["14"]
    E --> H["4"]
    E --> I["7"]

6.4.2 查找¶

// 在 BST 中查找值为 val 的节点
TreeNode* searchBST(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;       // 未找到
    if (root->val == val) return root;          // 找到
    if (val < root->val) return searchBST(root->left, val);   // 在左子树中查找
    return searchBST(root->right, val);                        // 在右子树中查找
}

6.4.3 插入¶

// 在 BST 中插入值为 val 的节点，返回根节点
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);  // 找到插入位置

    if (val < root->val) {
        root->left = insertIntoBST(root->left, val);   // 插入左子树
    } else {
        root->right = insertIntoBST(root->right, val);  // 插入右子树
    }
    return root;
}

6.4.4 删除¶

删除是 BST 最复杂的操作，分三种情况：

叶子节点：直接删除
只有一个子节点：用子节点替代
有两个子节点：用右子树的最小节点（或左子树的最大节点）替代

// 找到以 root 为根的子树中的最小节点
TreeNode* findMin(TreeNode* root) {
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

// 在 BST 中删除值为 key 的节点，返回根节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return nullptr;

    if (key < root->val) {
        root->left = deleteNode(root->left, key);   // 在左子树中删除
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);  // 在右子树中删除
    } else {
        // 找到要删除的节点
        // 情况 1 和 2：只有一个子节点或没有子节点
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // 情况 3：有两个子节点
        // 找右子树中的最小节点作为替代
        TreeNode* successor = findMin(root->right);
        root->val = successor->val;  // 用后继节点的值替代
        root->right = deleteNode(root->right, successor->val);  // 删除后继节点
    }
    return root;
}

时间复杂度分析：

操作	平均	最坏（退化为链表）
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

BST 的退化问题

如果按有序序列依次插入 BST，会退化为一条链表，所有操作变成 O(n)。这就是需要平衡树的原因。

6.5 平衡树简介¶

6.5.1 为什么需要平衡树¶

当 BST 退化为链表时，操作效率从 O(log n) 退化为 O(n)。平衡树通过旋转操作保持树的高度为 O(log n)。

6.5.2 AVL 树¶

AVL 树是最先发明的自平衡二叉搜索树。它保证任意节点的左右子树高度差不超过 1。

graph TD
    subgraph "AVL 树的旋转操作"
        A["左旋 (Left Rotate)"] --> A1["将右子节点提升为根，原根变为左子"]
        B["右旋 (Right Rotate)"] --> B1["将左子节点提升为根，原根变为右子"]
        C["左右旋 (LR)"] --> C1["先对左子左旋，再对根右旋"]
        D["右左旋 (RL)"] --> D1["先对右子右旋，再对根左旋"]
    end

AVL 树的平衡因子： 每个节点的左子树高度减去右子树高度，值为 -1、0 或 1。

6.5.3 红黑树¶

红黑树是另一种自平衡二叉搜索树，通过节点着色（红/黑）和旋转来维持平衡。

红黑树的性质：

每个节点是红色或黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的子节点必须是黑色（不能有两个连续的红色节点）
从任意节点到其叶子的所有路径包含相同数量的黑色节点

竞赛中的平衡树

在 ACM 竞赛中，通常不需要手写 AVL 或红黑树。C++ STL 的 set、map 底层就是红黑树，直接使用即可。了解基本概念有助于理解 set/map 的操作复杂度（均为 O(log n)）。

6.6 堆（优先队列）¶

与 5.7 的分工

堆的完整实现（手写堆模板、插入/删除、STL priority_queue 用法）见 5.7 堆与优先队列，堆排序完整程序见 3.1.6。本节从树（完全二叉树）的视角补充理解：堆就是一棵用数组存储的完全二叉树，上浮/下沉本质是沿树的一条链移动。

6.6.1 建堆¶

将一个无序数组调整为堆的过程叫做建堆（Heapify）。

#include <iostream>
#include <vector>
using namespace std;

// 向下调整：将以 i 为根的子树调整为最大堆
// n: 堆的大小
void siftDown(vector<int>& arr, int n, int i) {
    int largest = i;          // 假设当前节点最大
    int left = 2 * i + 1;     // 左子节点
    int right = 2 * i + 2;    // 右子节点

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr[i], arr[largest]);  // 交换
        siftDown(arr, n, largest);   // 递归调整
    }
}

// 建堆：从最后一个非叶子节点开始，依次向下调整
void buildMaxHeap(vector<int>& arr) {
    int n = arr.size();
    // 最后一个非叶子节点的下标为 n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }
}

建堆的时间复杂度： O(n)（不是 O(n log n)，数学证明表明是线性的）

6.6.2 堆排序（树视角回顾）¶

利用堆进行排序：建堆后，每次取出堆顶（最大值），放到末尾。从树的视角看：

建最大堆：把整棵完全二叉树调整为"每个结点都不小于其子结点"
反复摘取树根：将根（最大值）与"最后一层最右边的结点"交换，树的规模减一，再对新根做一次下沉

每次下沉最多走一条从根到叶的链，链长即树的高度 O(log n)，共 n 轮，故堆排序时间复杂度为 O(n log n)，原地交换，空间 O(1)。

完整代码

堆排序的完整可运行程序见 3.1.6 堆排序，此处不再重复。

6.6.3 插入与删除（树视角回顾）¶

插入：把新元素放在完全二叉树"最后一层最右边的下一个空位"（数组末尾），然后上浮——沿"结点 → 父结点"这条链最多爬到根，比较交换 O(log n) 次
删除堆顶：用"最后一个结点"顶替根，再下沉——每层选较大的孩子交换，最多走到叶子，同样是 O(log n)

两种操作都只沿树上的一条链移动，这正是堆所有操作复杂度为 O(log n) 的树结构根源。siftUp/insert/pop 的模板代码见 5.7.2 手写堆，与本节的树视角一一对应。

6.7 树的递归思维¶

树本身就是递归定义的结构，因此递归是解决树问题最自然的方式。

6.7.1 自顶向下（Top-Down）¶

从根节点出发，将信息向下传递给子节点。类似前序遍历。

// 示例：求二叉树的最大深度
// 自顶向下：将当前深度传递给子节点
int maxDepth = 0;

void dfs(TreeNode* node, int depth) {
    if (node == nullptr) {
        maxDepth = max(maxDepth, depth);  // 越过叶子（空结点），结算路径深度
        return;
    }
    dfs(node->left, depth + 1);   // 向左子树传递深度 +1
    dfs(node->right, depth + 1);  // 向右子树传递深度 +1
}

// 调用: dfs(root, 0);

6.7.2 自底向上（Bottom-Up）¶

从叶子节点出发，将子树的结果汇总返回给父节点。类似后序遍历。

// 示例：求二叉树的最大深度
// 自底向上：子树返回深度，父节点取最大值 +1
int maxDepthV2(TreeNode* node) {
    if (node == nullptr) return 0;  // 空节点深度为 0

    int leftDepth = maxDepthV2(node->left);   // 左子树深度
    int rightDepth = maxDepthV2(node->right);  // 右子树深度

    return max(leftDepth, rightDepth) + 1;  // 当前节点深度
}

如何选择自顶向下还是自底向上？

自顶向下：适合在遍历过程中累积信息（如路径和、路径个数）
自底向上：适合需要汇总子树信息的问题（如最大深度、是否平衡、直径）
如果需要同时使用左右子树的信息，通常用自底向上

6.7.3 经典例题：二叉树的最大深度（LeetCode 104）¶

// 方法：递归（自底向上）
// 思路：当前节点的最大深度 = max(左子树深度, 右子树深度) + 1
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

6.7.4 经典例题：判断是否是平衡二叉树（LeetCode 110）¶

// 方法：递归（自底向上），一次遍历
// 思路：在求深度的同时判断是否平衡
// 返回值：子树高度（若不平衡返回 -1）
int getHeight(TreeNode* node) {
    if (node == nullptr) return 0;

    int leftHeight = getHeight(node->left);
    if (leftHeight == -1) return -1;  // 左子树不平衡

    int rightHeight = getHeight(node->right);
    if (rightHeight == -1) return -1;  // 右子树不平衡

    // 左右子树高度差超过 1，不平衡
    if (abs(leftHeight - rightHeight) > 1) return -1;

    return max(leftHeight, rightHeight) + 1;  // 返回当前子树高度
}

bool isBalanced(TreeNode* root) {
    return getHeight(root) != -1;
}

时间复杂度： O(n)，每个节点只访问一次。

6.7.5 经典例题：二叉树的直径（LeetCode 543）¶

// 方法：递归（自底向上）
// 思路：直径 = 经过某个节点的最长路径 = 左子树深度 + 右子树深度
int diameter = 0;

int depth(TreeNode* node) {
    if (node == nullptr) return 0;

    int leftDepth = depth(node->left);    // 左子树深度
    int rightDepth = depth(node->right);  // 右子树深度

    // 经过当前节点的路径长度 = 左深度 + 右深度
    diameter = max(diameter, leftDepth + rightDepth);

    return max(leftDepth, rightDepth) + 1;  // 返回当前子树深度
}

int diameterOfBinaryTree(TreeNode* root) {
    depth(root);
    return diameter;
}

6.8 树的常见技巧¶

6.8.1 Morris 遍历简介¶

Morris 遍历是一种O(1) 空间的二叉树遍历算法，不使用栈也不使用递归。

核心思想：利用叶子节点的空指针（原本为 nullptr 的 right 指针）建立临时线索，遍历完成后恢复原树。

// Morris 中序遍历（空间复杂度 O(1)）
vector<int> morrisInorder(TreeNode* root) {
    vector<int> res;
    TreeNode* cur = root;

    while (cur != nullptr) {
        if (cur->left == nullptr) {
            // 没有左子树，直接访问当前节点
            res.push_back(cur->val);
            cur = cur->right;
        } else {
            // 有左子树，找到左子树的最右节点（前驱节点）
            TreeNode* predecessor = cur->left;
            while (predecessor->right != nullptr && predecessor->right != cur) {
                predecessor = predecessor->right;
            }

            if (predecessor->right == nullptr) {
                // 第一次到达：建立线索
                predecessor->right = cur;
                cur = cur->left;
            } else {
                // 第二次到达：说明左子树已遍历完，恢复树结构
                predecessor->right = nullptr;
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return res;
}

遍历方式	空间复杂度	说明
递归遍历	O(h)	h 为树高，递归栈深度
迭代遍历（栈）	O(h)	显式栈
Morris 遍历	O(1)	利用叶子空指针建线索

Morris 遍历的适用场景

Morris 遍历主要用于面试和理论分析。在竞赛中，递归和栈迭代更常用，因为实现简单且不易出错。了解 Morris 遍历有助于深入理解二叉树遍历的本质。

6.8.2 树的常见技巧总结¶

技巧	适用场景	示例
递归分解	大多数树问题	最大深度、是否平衡
后序遍历	需要汇总子树信息	直径、路径和
前序遍历	需要向下传递信息	路径打印、序列化
BFS 层序	按层处理	层序遍历、锯齿遍历
哈希表辅助	需要快速查找	节点映射、祖先查询
返回特殊值	用返回值传递状态	-1 表示不平衡

6.8.3 经典例题：二叉树的最近公共祖先（LeetCode 236）¶

// 方法：递归（自底向上）
// 思路：
//   - 如果当前节点是 p 或 q，返回当前节点
//   - 如果左右子树分别找到了 p 和 q，当前节点就是 LCA
//   - 否则返回找到 p 或 q 的那一侧
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr;    // 空节点
    if (root == p || root == q) return root; // 找到 p 或 q

    TreeNode* left = lowestCommonAncestor(root->left, p, q);   // 在左子树中查找
    TreeNode* right = lowestCommonAncestor(root->right, p, q); // 在右子树中查找

    if (left != nullptr && right != nullptr) return root;  // 左右各找到一个，当前节点是 LCA
    if (left != nullptr) return left;   // 都在左子树
    return right;                        // 都在右子树（或都没找到）
}

时间复杂度： O(n)

6.9 一般树上的 DFS 与树形 DP 初步¶

前面几节的例题都建立在二叉树（left/right 指针）上，但竞赛中更常见的是一般树：n 个结点、n-1 条边，孩子个数不定，用 6.1.3 的邻接表存储。在一般树上做 DFS 只需解决一个问题：无向边会存两遍，递归时要记住父结点 fa，防止往回走。

6.9.1 模板：子树大小统计¶

sz[u] 表示以 u 为根的子树的结点数，等于"自己 + 所有孩子子树大小之和"，是典型的自底向上（后序）汇总：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;

vector<int> adj[MAXN];  // 邻接表（见 6.1.3）
int sz[MAXN];           // sz[u]: 以 u 为根的子树的结点数

// 统计子树大小：fa 是 u 的父结点，防止往回走
void dfsSize(int u, int fa) {
    sz[u] = 1;  // 先算上 u 自己
    for (int v : adj[u]) {
        if (v == fa) continue;   // 无向边会存两遍，跳过父结点
        dfsSize(v, u);
        sz[u] += sz[v];          // 累加每棵子树的大小
    }
}
// 调用: dfsSize(root, 0);  结点编号从 1 开始时，用 0 充当"虚拟父结点"

时间复杂度： O(n)。每个结点恰好被访问一次，每条边恰好被走两遍（u→v 与 v→u 各一次判断）。

这个"把孩子的信息汇总到父亲"的模式，正是树形 DP 的雏形——sz[u] 就是一个最简单的 DP 状态。

6.9.2 例题：树的直径（两次 DFS）¶

SPOJ PT07Z (Longest path in a tree) 题意：给定一棵 n 个结点的无权树，求直径——树上最长路径的边数。

结论： 从任意结点出发 DFS，找到离它最远的结点 u；再从 u 出发 DFS，找到离 u 最远的结点 v。则 u 到 v 的距离就是直径（可用反证法证明 u 一定是某条直径的端点）。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;

vector<int> adj[MAXN];
int dist_[MAXN];  // dist_[i]: i 到本次 DFS 出发点的距离（边数）

void dfs(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        dist_[v] = dist_[u] + 1;
        dfs(v, u);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 第一次 DFS：从任意点（取 1）出发，找最远点 u
    dist_[1] = 0;
    dfs(1, 0);
    int u = 1;
    for (int i = 1; i <= n; i++) if (dist_[i] > dist_[u]) u = i;

    // 第二次 DFS：从 u 出发，最远距离即直径
    dist_[u] = 0;
    dfs(u, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dist_[i]);

    cout << ans << endl;
    return 0;
}

运行示例： 输入下面这棵 6 结点的树，直径是路径 3-2-4-5-6，共 4 条边：

时间复杂度： O(n)，两次 DFS 各走一遍整棵树。

与 6.7.5 对比：LeetCode 543 用"左深度 + 右深度"在二叉树上求直径（一次后序 DFS），本题的两次 DFS 则适用于任意树；一般树上也可以用一次 DFS 求直径（维护每个结点向下的最长/次长链），那已是标准的树形 DP 写法。

一般树 DFS 的常见坑

忘记 if (v == fa) continue;——无向边存了两遍，会在父子之间来回死递归
判断"回边"用的是父结点而不是 visited 数组：树保证无环，记父结点即可，省一个数组（图上则必须用 visited，见第 11 章）
n 达到 10^5 以上时递归深度可能爆栈（链状树深度即 n），比赛中可改用显式栈或 BFS 求距离
结点编号从 1 开始时，根的"父结点"传 0；若编号从 0 开始，传 -1

树形 DP 在第 10 章展开

子树大小、向下最长链都是"孩子汇总到父亲"的树形 DP 特例。完整的树形 DP（打家劫舍 III 等，10.1 节）与换根 DP（10.2 节）将在第 10 章动态规划进阶系统讲解。

练习题¶

LeetCode 暑假扩展2 二叉树¶

题号	题目	难度	链接	完成	备注
226	Invert Binary Tree	Easy	https://leetcode.com/problems/invert-binary-tree/	- [ ]
110	Balanced Binary Tree	Easy	https://leetcode.com/problems/balanced-binary-tree/	- [ ]
257	Binary Tree Paths	Easy	https://leetcode.com/problems/binary-tree-paths/	- [ ]
617	Merge Two Binary Trees	Easy	https://leetcode.com/problems/merge-two-binary-trees/	- [ ]
203	Remove Linked List Elements	Easy	https://leetcode.com/problems/remove-linked-list-elements/	- [ ]	实际考点：链表（见第 5 章）
102	Binary Tree Level Order Traversal	Medium	https://leetcode.com/problems/binary-tree-level-order-traversal/	- [ ]
230	Kth Smallest Element in a BST	Medium	https://leetcode.com/problems/kth-smallest-element-in-a-bst/	- [ ]
173	Binary Search Tree Iterator	Medium	https://leetcode.com/problems/binary-search-tree-iterator/	- [ ]	原 285 为会员题，已替换（同为 BST 中序）
222	Count Complete Tree Nodes	Medium	https://leetcode.com/problems/count-complete-tree-nodes/	- [ ]
236	Lowest Common Ancestor of a Binary Tree	Medium	https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/	- [ ]
814	Binary Tree Pruning	Medium	https://leetcode.com/problems/binary-tree-pruning/	- [ ]
778	Swim in Rising Water	Hard	https://leetcode.com/problems/swim-in-rising-water/	- [ ]	实际考点：图论（二分/堆 + BFS，见第 11 章）
968	Binary Tree Cameras	Hard	https://leetcode.com/problems/binary-tree-cameras/	- [ ]
2402	Meeting Rooms III	Hard	https://leetcode.com/problems/meeting-rooms-iii/	- [ ]
732	My Calendar III	Hard	https://leetcode.com/problems/my-calendar-iii/	- [ ]

寒假二叉树相关¶

题号	题目	难度	链接	完成
94	Binary Tree Inorder Traversal	Easy	https://leetcode.com/problems/binary-tree-inorder-traversal/	- [ ]
114	Flatten Binary Tree to Linked List	Medium	https://leetcode.com/problems/flatten-binary-tree-to-linked-list/	- [ ]
543	Diameter of Binary Tree	Easy	https://leetcode.com/problems/diameter-of-binary-tree/	- [ ]
124	Binary Tree Maximum Path Sum	Hard	https://leetcode.com/problems/binary-tree-maximum-path-sum/	- [ ]

扩展5 二叉树+链表¶

题号	题目	难度	链接	完成
206	Reverse Linked List	Easy	https://leetcode.com/problems/reverse-linked-list/	- [ ]
141	Linked List Cycle	Easy	https://leetcode.com/problems/linked-list-cycle/	- [ ]
876	Middle of the Linked List	Easy	https://leetcode.com/problems/middle-of-the-linked-list/	- [ ]
234	Palindrome Linked List	Easy	https://leetcode.com/problems/palindrome-linked-list/	- [ ]
342	Power of Four	Easy	https://leetcode.com/problems/power-of-four/	- [ ]
92	Reverse Linked List II	Medium	https://leetcode.com/problems/reverse-linked-list-ii/	- [ ]
2	Add Two Numbers	Medium	https://leetcode.com/problems/add-two-numbers/	- [ ]
86	Partition List	Medium	https://leetcode.com/problems/partition-list/	- [ ]
61	Rotate List	Medium	https://leetcode.com/problems/rotate-list/	- [ ]
109	Convert Sorted List to Binary Search Tree	Medium	https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/	- [ ]
432	All O`one Data Structure	Hard	https://leetcode.com/problems/all-oone-data-structure/	- [ ]
460	LFU Cache	Hard	https://leetcode.com/problems/lfu-cache/	- [ ]
1206	Design Skiplist	Hard	https://leetcode.com/problems/design-skiplist/	- [ ]
1235	Maximum Profit in Job Scheduling	Hard	https://leetcode.com/problems/maximum-profit-in-job-scheduling/	- [ ]

第六章 树与二叉树¶