二叉树操作

约 1084 字 预计阅读 4 分钟 本文访问量 0 数据结构与算法 二叉树

多为力扣题目，旨在熟悉二叉树的各种操作，以及深搜时通过子树汇总信息的思想

定义树：

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) {}
};

计算高度（最大深度）

问题：传入一个根节点，计算该树的高度

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

计算最小深度

递归实现：

int minDepth(TreeNode* root)
{
    if(!root){
        return 0;
    }
    if(!root->left && !root->right){
        return 1;
    }

    int minn = 1e9; // 找左右子树的最小
    if(root->left){
        minn = min(minDepth(root->left),minn);
    }
    if(root->right){
        minn = min(minDepth(root->right),minn);
    }

    return minn+1;
}

迭代实现：思路比较清晰，逐层操作

计算直径

二叉树的直径是指树中任意两个节点之间最长路径的长度，两节点之间路径的长度由它们之间边数表示

注意：这条最长路径可能不经过根节点

解法：遍历每个节点，计算该节点的两个子树的最大深度和，取最大者

计算坡度

  • 一个树的节点的坡度定义为，该节点左子树的节点之和和右子树节点之和的差的绝对值
  • 如果没有左子树的话，左子树的节点之和为 0；没有右子树的话也是一样。空结点的坡度是 0
  • 整个树 的坡度就是其所有节点的坡度之和

官方题解：

int ans = 0;
int findTilt(TreeNode* root) {
    dfs(root);
    return ans;
}

int dfs(TreeNode* root){
    if(!root) return 0;
    int lsum = dfs(root->left);
    int rsum = dfs(root->right);
    ans += abs(lsum - rsum);
    return root->val + lsum + rsum; // 返回给上层节点使用
}

判断相同

问题：传入两个根节点，判断这两棵树是否相同

可能会想到通过前序和中序遍历结果来判断，但如果两棵树的每个元素都相同而只是结构不同，则所有遍历方式的结果都相同；除非加入判断左右子树的标志，而这种情况下只使用一种遍历方式结果

bool isSameTree(TreeNode* p, TreeNode* q) {
    return pre(p) == pre(q);
}

string pre(TreeNode* root){
    if(root == nullptr){
        return "";
    }
    string s;
    s.append(to_string(root->val));
    s+='l';
    s.append(pre(root->left));
    s+='r';
    s.append(pre(root->right));
    return s;
}

官方题解:

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    } else if (p == nullptr || q == nullptr) {
        return false;
    } else if (p->val != q->val) {
        return false;
    } else {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}

判断对称

问题：传入一个根节点，判断该树是否对称

对称树的特点是：对于每个节点，其左子树和右子树是对称的，即左子树的左节点等于右子树的右节点，左子树的右节点等于右子树的左节点

官方题解（递归）:

bool isSymmetric(TreeNode* root) {
    return check(root->left, root->right);
}

bool check(TreeNode* u,TreeNode* v){
    if(!u && !v) return true;
    if(!u || !v || u->val != v->val) return false;
    return check(u->left, v->right) && check(u->right, v->left);
}

官方题解（迭代）:

bool isSymmetric(TreeNode* root) {
    return check(root->left,root->right);
}

bool check(TreeNode* u,TreeNode* v){
    queue<TreeNode*> q;
    q.push(u); q.push(v);
    while(!q.empty()){
        u = q.front(); q.pop();
        v = q.front(); q.pop();
        if(!u && !v){
            continue;
        }
        if((!u || !v) || u->val != v->val){
            return false;
        }

        q.push(u->left);
        q.push(v->right);

        q.push(u->right);
        q.push(v->left);
    }
    return true;
}

判断平衡

平衡二叉树是指所有节点的左右子树的高度相差不超过 1 的二叉树

先上一个错误代码

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

bool isBalanced(TreeNode* root) {
    if(!root){
        return true;
    }
    return abs(getHeight(root->left) - getHeight(root->right)) <= 1;
}

错误之处在于只判断了根，而没有考虑每个子树

        1      <-- 根节点：左高 3，右高 2。差 1。你的代码判定：平衡 (Pass)
       / \
      2   3    <-- 节点 2：左高 2，右高 0。差 2。实际情况：不平衡 (Fail)
     /     \
    4       5
   /
  6

正确做法要自顶向下递归，遍历每个节点，计算其左右子树的高度，并判断是否平衡

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

bool isBalanced(TreeNode* root) {
    if(!root){
        return true;
    }
    if(abs(getHeight(root->left)-getHeight(root->right)) > 1){
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

路径总和

问题：断二叉树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和

先放个错误代码：

bool hasPathSum(TreeNode* root, int targetSum) {
    if(!root) return false;
    return helper(root, targetSum, 0);
}

bool helper(TreeNode* root, int targetSum, int sum) {
    if(!root){
        if(sum == targetSum) return true;
        return false;
    }

    return helper(root->left, targetSum, sum + root->val)
            || helper(root->right, targetSum, sum + root->val);
}

错在把叶子节点的判断视为了 !root 的前驱

    1 // 目标和为 1，此时进入 1 的右子节点时会错误地把 1 当作叶子结点
   /
  2

我的AC代码：

bool hasPathSum(TreeNode* root, int targetSum) {
    if(!root) return false;
    return helper(root, targetSum, 0);
}

bool helper(TreeNode* root, int targetSum, int sum) {
    if(!root) return false;
    if(!root->left && !root->right){ // 修正
        if(sum+root->val == targetSum) return true;
        return false;
    }

    return helper(root->left, targetSum, sum + root->val)
            || helper(root->right, targetSum, sum + root->val);
}

官方题解：

bool hasPathSum(TreeNode* root, int targetSum) {
    if(!root) return false;
    targetSum -= root->val;
    if(!root->left && !root->right) return targetSum == 0;
    return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}

如果要把所有路径都求出来呢？

class Solution {
public:
   vector<vector<int>> ret;
   vector<int> path;

   void dfs(TreeNode* root, int targetSum) {
       if (root == nullptr) {
           return;
       }
       path.emplace_back(root->val);
       targetSum -= root->val;
       if (root->left == nullptr && root->right == nullptr && targetSum == 0) {
           ret.emplace_back(path);
       }
       dfs(root->left, targetSum);
       dfs(root->right, targetSum);
       path.pop_back(); // <-- 注意这里
   }

   vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
       dfs(root, targetSum);
       return ret;
   }
};

最近公共祖先 // todo

思路：后序遍历。左边找到了吗？右边找到了吗？如果左右都找到了，那我就是祖先。

以下为与二叉搜索树相关

验证二叉搜索树

当然，利用中序遍历有序的方式也可以进行验证，但这里讨论其他方法

先放个错误代码：

bool isValidBST(TreeNode* root) {
    if (root == nullptr) return true;
    if (root->left && root->left->val >= root->val) return false;
    if (root->right && root->right->val <= root->val) return false;
    return isValidBST(root->left) && isValidBST(root->right);
}

只能通过大部分样例（77/86），误区在于该代码只比较了上下层的关系，跨层关系未进行判断

  10
 /  \
5    15
    /
   6  <-- 错误在这里

而二叉树搜索树定义为：“左子树所有节点值 <= 根节点值，右子树所有节点值 >= 根节点值” 的二叉树，左、右子树也需满足该规则

比较的不应是上下层，而是根与左右子树各节点的最值

我的初版AC代码：

bool isValidBST(TreeNode* root) {
    if(!root) return true;
    bool f1, f2;
    if(root->left){
        f1 = root->val >= maxsub(root->left);
    }
    else{
        f1 = true;
    }
    if(root->right){
        f2 = root->val <= minsub(root->right);
    }
    else{
        f2 = true;
    }
    return isValidBST(root->left) && isValidBST(root->right) && f1 && f2;
}

int maxsub(TreeNode* root){
    if(!root) return -1e9;
    int maxx = root->val;
    if(root->left){
        maxx = max(maxsub(root->left),maxx);
    }
    if(root->right){
        maxx = max(maxsub(root->right),maxx);
    }
    return maxx;
}
int minsub(TreeNode* root){
    if(!root) return 1e9;
    int minn = root->val;
    if(root->left){
        minn = min(minsub(root->left),minn);
    }
    if(root->right){
        minn = min(minsub(root->right),minn);
    }
    return minn;
}

当然，这个 isValidBST 还可以再简洁化：

bool isValidBST(TreeNode* root) {
    if(!root) return true;
    if(root->left && root->val <= maxsub(root->left)){
        return false;
    }
    if(root->right && root->val >= minsub(root->right)){
        return false;
    }
    return isValidBST(root->left) && isValidBST(root->right);
}

但依然比较丑陋，性能也比较低下。下面为官方题解：

bool helper(TreeNode* root, long long lower, long long upper) {
    if(root == nullptr) return true;
    if(root->val <= lower || root -> val >= upper){
        return false;
    }
    return helper(root->left, lower, root->val) && helper(root->right, root->val, upper);
}
bool isValidBST(TreeNode* root) {
    return helper(root, -1e18, 1e18);
}

有序数组转二叉搜索树

问题：给定一个整数数组 nums，其中元素已经按升序排列，将其转换为一棵平衡二叉搜索树

选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return helper(nums, 0, nums.size()-1);
}

TreeNode* helper(vector<int>& nums, int l, int r){
    if(l > r) return nullptr;
    int mid = (l+r)/2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = helper(nums, l, mid-1);
    root->right = helper(nums, mid+1, r);
    return root;
}

有序链表转二叉搜索树？ 同理可用上述方法，获取中间节点可以采用快慢指针的方式，快指针一次移两个单位，慢指针移一个，当快指针到达边界时，慢指针即指向中间节点 或者还有另一种也是通用的方法，bfs 建树 + dfs 填值 ？

标题：二叉树操作

作者：Zwing

创建于：2026-01-16 19:10:18

更新于：2026-08-07 16:17:52

链接：https://zanytriumph.github.io/posts/二叉树操作.html

版权声明：本文章采用 CC BY-NC-SA 4.0 进行许可