2318 个字词
12 分钟
二叉树
首次发布: 2025-07-30
... 次访问
Course Notes
Algorithms

二叉树是数据结构中的重要内容，其操作主要依赖于遍历思想，包括深度优先搜索（DFS）和广度优先搜索（BFS）。本笔记将围绕二叉树的常见问题，按照原理和例题的模式进行组织。

树的遍历与属性#

树的遍历是解决大多数二叉树问题的基础。通过递归或迭代的方式，我们可以访问树中的每一个节点，从而检查或计算树的各种属性，如深度、节点总数、是否对称等。

深度/广度优先搜索#

  • 深度优先搜索 (DFS)：优先访问子树，直到最深的节点，然后回溯。通常使用递归（前序、中序、后序遍历）或栈实现。
  • 广度优先搜索 (BFS)：按层级顺序访问节点，从根节点开始，逐层向下。通常使用队列实现。

Example Problem Leetcode 100. 相同的树

原理： 判断两棵树是否相同，可以通过深度优先搜索（DFS）同时遍历两棵树。在每一步递归中，我们比较当前两个节点的值是否相等，并递归地检查它们的左右子树是否也分别相同。

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

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true; // 两者都为空，相同
        if (!p || !q || p->val != q->val) return false; // 一个为空或值不同，不相同
        
        // 递归比较左右子树
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Example Problem Leetcode 110. 平衡二叉树

原理： 一棵平衡二叉树的定义是：对于任意节点，其左右子树的高度差不超过 1。我们可以通过后序遍历（一种 DFS）来解决这个问题。在遍历每个节点时，我们计算其左右子树的高度，如果高度差大于 1，则该树不平衡。如果平衡，就返回当前节点的高度。使用 -1 或其他哨兵值来表示不平衡状态可以提前终止递归。

class Solution {
public:
    // 返回树的高度，如果不是平衡二叉树则返回 -1
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return std::max(leftHeight, rightHeight) + 1;
    }

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

路径总和问题#

在二叉树中，“路径”通常指从一个节点到另一个节点的序列。路径总和问题是二叉树中的一类经典问题，通常需要使用深度优先搜索来遍历所有可能的路径，并检查它们的和是否满足特定条件。

Example Problem Leetcode 112. 路径总和

原理： 判断是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值之和等于目标值。我们可以使用 DFS，在递归过程中，将目标值减去当前节点的值，然后继续在子树中寻找剩余的目标值。当到达叶子节点时，如果剩余的目标值恰好等于叶子节点的值，则找到了一条有效路径。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        
        // 如果是叶子节点，检查路径和是否满足条件
        if (!root->left && !root->right) {
            return targetSum == root->val;
        }
        
        // 递归地在左右子树中寻找
        return hasPathSum(root->left, targetSum - root->val) || 
               hasPathSum(root->right, targetSum - root->val);
    }
};

Example Problem Leetcode 437. 路径总和 III

原理： 寻找路径和等于目标值的路径数量，路径不一定需要从根节点开始或在叶子节点结束。直接的 DFS 会导致重复计算。我们可以使用“前缀和”的思想来优化。在 DFS 遍历时，我们用一个哈希表记录从根到当前节点路径上所有可能的前缀和及其出现的次数。在每个节点，我们检查 (当前前缀和 - 目标值) 是否在哈希表中，如果是，则说明找到了满足条件的路径。

#include <unordered_map>

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        std::unordered_map<long long, int> prefixSumCount;
        prefixSumCount[0] = 1; // 前缀和为0的路径有1条（空路径）
        return dfs(root, 0, targetSum, prefixSumCount);
    }

private:
    int dfs(TreeNode* node, long long currentSum, int targetSum, std::unordered_map<long long, int>& prefixSumCount) {
        if (!node) return 0;

        currentSum += node->val;
        int count = 0;
        // 寻找 `currentSum - targetSum` 的前缀和
        if (prefixSumCount.count(currentSum - targetSum)) {
            count = prefixSumCount[currentSum - targetSum];
        }

        // 更新前缀和哈希表
        prefixSumCount[currentSum]++;
        
        // 递归进入左右子树
        count += dfs(node->left, currentSum, targetSum, prefixSumCount);
        count += dfs(node->right, currentSum, targetSum, prefixSumCount);

        // 回溯：恢复哈希表状态，以免影响兄弟分支
        prefixSumCount[currentSum]--;
        
        return count;
    }
};

Example Problem Leetcode 124. 二叉树中的最大路径和

原理： 寻找任意两个节点之间路径的最大和。路径可以不经过根节点。对于每个节点，穿过它的最大路径和可能是 左子树最大贡献 + 节点值 + 右子树最大贡献。我们使用 DFS 进行后序遍历，对于每个节点，计算并返回它能为“父节点”提供的最大路径贡献（即 节点值 + max(左贡献, 右贡献)）。同时，用一个全局变量来更新我们目前找到的最大路径和。

#include <algorithm>
#include <limits>

class Solution {
private:
    int maxSum = std::numeric_limits<int>::min();

public:
    // 返回从该节点出发向下的最大路径和
    int maxGain(TreeNode* node) {
        if (!node) return 0;

        // 递归计算左右子节点的最大贡献值
        // 如果子树贡献为负，则不选择该子树
        int leftGain = std::max(maxGain(node->left), 0);
        int rightGain = std::max(maxGain(node->right), 0);

        // 更新全局最大路径和
        // 路径可以穿过当前节点，连接左右子树
        int priceNewPath = node->val + leftGain + rightGain;
        maxSum = std::max(maxSum, priceNewPath);

        // 返回对父节点的最大贡献值
        return node->val + std::max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

树的结构修改#

这类问题要求在原地修改树的结构，例如将二叉树转换为链表。通常需要利用特定的遍历顺序（如后序遍历）来确保在修改节点指针时不会丢失子树信息。

Example Problem Leetcode 114. 二叉树展开为链表

原理： 将二叉树原地展开为单链表，顺序为前序遍历的顺序。如果我们采用后序遍历（右-左-根）的思路，可以更方便地进行原地修改。

  1. 递归地展开右子树。
  2. 递归地展开左子树。
  3. 将当前节点的右指针指向已展开的原左子树。
  4. 将原左子树置空。
  5. 找到原左子树展开后链表的末尾，将其右指针指向已展开的原右子树。
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;

        // 递归展开左右子树
        flatten(root->left);
        flatten(root->right);

        // 保存原有的左右子树
        TreeNode* left = root->left;
        TreeNode* right = root->right;

        // 将左子树置空，并将右指针指向原左子树
        root->left = nullptr;
        root->right = left;

        // 找到新右子树（原左子树）的末尾
        TreeNode* p = root;
        while (p->right) {
            p = p->right;
        }

        // 将原右子树连接到末尾
        p->right = right;
    }
};

最近公共祖先 (LCA)#

最近公共祖先（LCA）是指在树中，离两个节点最近的共同祖先。这是树结构中的一个核心概念。

Example Problem Leetcode 236. 二叉树的最近公共祖先

原理： 使用 DFS 递归查找。从根节点开始，如果当前节点是 p 或 q 之一，则它就是LCA（如果另一个节点在它的子树中）。否则，递归地在左右子树中查找 p 和 q。

  • 如果 p 和 q 分别位于当前节点的左右子树中，则当前节点是 LCA。
  • 如果 p 和 q 都在左子树中，则 LCA 也在左子树中，向左递归。
  • 如果 p 和 q 都在右子树中，则 LCA 也在右子树中，向右递归。
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) return root; // p, q 分布在两侧
        if (left) return left;           // p, q 都在左侧
        return right;                    // p, q 都在右侧
    }
};

Example Problem Leetcode 235. 二叉搜索树的最近公共祖先

原理： 对于二叉搜索树（BST），其有序的特性可以让我们更高效地找到 LCA。

  • 如果 p 和 q 的值都小于当前节点的值，则 LCA 必定在左子树中。
  • 如果 p 和 q 的值都大于当前节点的值，则 LCA 必定在右子树中。
  • 如果当前节点的值介于 p 和 q 之间（或等于其中之一），则当前节点就是 LCA，因为 p 和 q 将会“分叉”。

这个性质允许我们使用迭代或递归进行一次性的查找，时间复杂度为 O(H)，其中 H 是树的高度。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* ancestor = root;
        while (true) {
            if (p->val < ancestor->val && q->val < ancestor->val) {
                ancestor = ancestor->left;
            } else if (p->val > ancestor->val && q->val > ancestor->val) {
                ancestor = ancestor->right;
            } else {
                // p 和 q 在当前节点的两侧或其中一个是当前节点
                break;
            }
        }
        return ancestor;
    }
};
二叉树
https://adalovelemon.github.io/blog/posts/content/coursenotes/algorithms/computertalgorithms/binarytree/
Author
Ada Lovelemon
Published at
2025-07-30

留言板

...
© 2026 Ada Lovelemon Site policy Astro theme powered