二叉树

概览

二叉树问题几乎都遵循同一个模板：递归处理左子树，递归处理右子树，然后在当前节点合并结果。关键在于明确「函数返回值的语义」——它应该向父节点传递什么信息，然后父节点如何利用这个信息。

万能递归模板

在写任何树题前，先明确三件事：① 递归函数返回值代表什么；② base case（空节点）返回什么；③ 当前节点如何用左右子树的返回值计算自己的答案。

ReturnType solve(TreeNode* root) {
    if (!root) return BASE_CASE;          // ① base case
    auto left  = solve(root->left);       // recurse left
    auto right = solve(root->right);      // recurse right
    return MERGE(root->val, left, right); // ③ combine
}

三种遍历顺序

复杂度

DFS 遍历（前中后序）

递归实现简洁自然；迭代实现用显式栈模拟调用栈，在树很深时可避免栈溢出。面试中迭代中序是高频考点。

递归实现（三种一体）

// Pre-order: Root → Left → Right
void preorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);    // visit root FIRST
    preorder(root->left, res);
    preorder(root->right, res);
}

// In-order: Left → Root → Right
void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);    // visit root IN MIDDLE
    inorder(root->right, res);
}

// Post-order: Left → Right → Root
void postorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    postorder(root->left, res);
    postorder(root->right, res);
    res.push_back(root->val);    // visit root LAST (subtrees already resolved)
}

迭代中序（最重要）

用显式栈模拟「一路向左，到底后弹出、访问、转右」的过程。cur 指针控制当前节点，不为 null 时持续压栈并向左走；为 null 时弹出栈顶访问并向右走。

迭代中序步骤

1. 初始化 cur = root，stack<TreeNode*> st
2. 外层循环：cur 不为 null 或栈不为空时继续
3. 内层循环：cur 不为 null 时持续压栈，cur = cur->left
4. 弹出栈顶：cur = st.top(); st.pop(); 访问 cur->val
5. 向右走：cur = cur->right，回到外层循环

C++ 实现

// Iterative in-order — avoids stack overflow on deep trees
vector<int> inorderIterative(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; } // go all the way left
        cur = st.top(); st.pop();
        res.push_back(cur->val);   // visit
        cur = cur->right;          // MUST move right (or infinite loop!)
    }
    return res;
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

常见错误

BFS 层序遍历

用队列按层处理节点：每轮循环前记录当前队列长度 sz，只处理这 sz 个节点（属于同一层），处理时将子节点入队。

核心模板

queue'<'TreeNode*'>' q; q.push(root)。外层 while (!q.empty()) 每次迭代处理一整层：int sz = q.size()，循环 sz 次 pop + 收集 + push children。这是层序所有变体的基础。

步骤

1. 根节点入队，res 存结果
2. while (!q.empty())：sz = q.size()，vector<int> level
3. 循环 sz 次：auto node = q.front(); q.pop(); level.push_back(node->val)
4. 若 node->left，入队；若 node->right，入队
5. res.push_back(level)，继续外层循环

C++ 实现

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();             // snapshot BEFORE inner loop
        vector<int> level;
        for (int i = 0; i < sz; i++) {
            auto 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;
}

层序变体

常见错误

BST 性质与验证

BST（二叉搜索树）性质：左子树所有节点 < 根 < 右子树所有节点。中序遍历结果严格递增。

核心性质

验证 BST：范围传递法

每个节点必须满足 lo < node->val < hi。递归传递范围：向左子树传 (lo, node->val)，向右子树传 (node->val, hi)。初始 lo = LLONG_MIN, hi = LLONG_MAX，防止 INT_MIN/INT_MAX 的边界问题。

步骤

1. 函数签名：bool isValidBST(TreeNode* root, long long lo, long long hi)
2. base case：root 为 null 返回 true
3. 若 root->val <= lo 或 root->val >= hi，返回 false
4. 递归：isValidBST(left, lo, root->val) && isValidBST(right, root->val, hi)

C++ 实现

// Range propagation: every node must satisfy lo < val < hi
bool isValidBST(TreeNode* root,
                long long lo = LLONG_MIN,
                long long hi = LLONG_MAX) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left,  lo,          root->val)
        && isValidBST(root->right, root->val,   hi);
}

常见错误

路径问题与树形 DP

路径类问题（最大路径和、直径）需要「后序思维」：先从子树收集信息，再在当前节点合并计算答案并向上传递。

最大路径和（LC 124）

关键：函数返回「经过 root 向上的最长单侧路径」（只能选左或右一侧），但同时在内部用 left + root + right 更新全局答案。注意路径值可能为负，取 max(arm, 0) 处理负子树。

1. 定义 dfs(node) → 以 node 为端点向上的最长路径长（含 node->val）
2. left = max(dfs(node->left), 0)；right = max(dfs(node->right), 0)
3. ans = max(ans, node->val + left + right)（当前节点作为路径最高点）
4. 返回 node->val + max(left, right)（向上只能选一侧）

二叉树直径（LC 543）

直径 = 任意两节点间最长路径经过的边数。等价于找 left_depth + right_depth 的最大值（不含根节点处的额外计数）。与最大路径和同构，把路径「和」换成「深度」即可。

最近公共祖先（LC 236）

递归：若 root 为 null 或等于 p/q，返回 root。分别在左右子树找 p 和 q；若左右各找到一个，则 root 即为 LCA；若只有一侧找到，返回那一侧（说明两个节点都在同一侧）。

C++ 参考实现

int ans = INT_MIN;

// Returns the longest single-arm path through root going upward
int dfs(TreeNode* root) {
    if (!root) return 0;
    int left  = max(dfs(root->left),  0); // discard negative arms
    int right = max(dfs(root->right), 0);
    ans = max(ans, root->val + left + right); // root as path peak
    return root->val + max(left, right);      // pass up best single arm
}

// LC 124 — Binary Tree Maximum Path Sum
int maxPathSum(TreeNode* root) {
    ans = INT_MIN;
    dfs(root);
    return ans;
}

// LC 236 — Lowest Common Ancestor (general binary tree)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    auto left  = lowestCommonAncestor(root->left,  p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root; // p and q on opposite sides
    return left ? left : right;     // both on the same side
}

常见错误

LeetCode 题型

按技术分类的高频二叉树题目。

遍历

BST

路径与树形 DP

构造与序列化