当前位置： 首页 > article >正文

代码随想录——二叉树（二）

article 2025/3/6 8:54:58

文章目录

      • 前言
      • 二叉树最大深度
      • 二叉树的最小深度
      • 翻转二叉树
      • 对称二叉树
      • 完全二叉树的节点个数
      • 平衡二叉树
      • 二叉树的所有路径
      • 左叶子之和
      • 找左下角的值
      • 路径总和
      • 从中序与后序序列构造二叉树
      • 最大二叉树
      • 合并二叉树
      • 二叉搜索树中的搜索
      • 验证二叉搜索树
      • 二叉搜索树的最小绝对差
      • 二叉树中的众数
      • 二叉树的最近公共祖先
      • 二叉搜索树的最近公共祖先
      • 二叉搜索树中的插入操作
      • 删除二叉搜索树中的节点
      • 修剪二叉搜索树
      • 将有序数组转换为二叉搜索树
      • 把二叉搜索树转换为累加树

前言

代码随想录系列也写了好几期了，我写代码随想录的题目主要是为了准备机试，这也是为什么我只用c语言的原因。而我更新文章是为了之后复习以及督促自己（看到有人点赞我真的很开心）。
然后是博客质量的问题，首先这个系列主要是为了日后复习的，所以很多是我了我自己看懂就行了，并没有很深刻地解释一些问题。还有一部分原因是我每天还要学习毕设的一些知识，我选了一个对我来说很有挑战的题目，因此要分配一些精力去学习，导致我没有很多的时间打磨的题解。最后谢谢大家的关注与点赞，希望可以帮助大家！

二叉树最大深度

104. 二叉树的最大深度

思路：DFS，递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int Max(int a,int b){
    return a>b?a:b;
}
int maxDepth(struct TreeNode* root) {
    if(root==NULL)return 0;
    return Max(maxDepth(root->left),maxDepth(root->right))+1;
}

二叉树的最小深度

111. 二叉树的最小深度

思路：DFS，递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int Min(int a,int b){
    return a<b?a:b;
}
int minDepth(struct TreeNode* root) {
    if(root==NULL)return 0;
    
    else if(root->left==NULL)return minDepth(root->right)+1;
    else if(root->right==NULL)return minDepth(root->left)+1; 
    else return Min(minDepth(root->left),minDepth(root->right))+1;
}

翻转二叉树

226. 翻转二叉树

思路：将每个节点的左右孩子交换，按照任意一种遍历均可

下面是先序遍历代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    //对于每个节点，交换左右孩子节点
    if(root==NULL)return root;
    else{
        
        struct TreeNode *temp=root->left;
        root->left=root->right;
        root->right=temp;
        invertTree(root->left);
        invertTree(root->right);
        
        return root;
    }
}

对称二叉树

101. 对称二叉树

思路：本来想着先用上一题的代码把二叉树翻转，然后通过比较翻转之后的树与原来的树是否相同判断原二叉树是否对称，但是我上面的代码直接改变了原二叉树的结构（不过思路应该是可行的）。然后发现直接比较根节点的左右子树是否对称就行了，逻辑和上面比较两个树是否相同差不多。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool ismirror(struct TreeNode* a,struct TreeNode* b){
    if(a==NULL&&b==NULL)return true;
    else if(a==NULL)return false;
    else if(b==NULL)return false;
    else{
        if(a->val!=b->val)return false;
        else{
            return (ismirror(a->left,b->right)&&ismirror(a->right,b->left));
        }
    }
}
bool isSymmetric(struct TreeNode* root) {
   
    return ismirror(root->left,root->right);
}

完全二叉树的节点个数

222. 完全二叉树的节点个数

思路一：遍历一遍二叉树并计数（不过这样就浪费了完全二叉树的条件）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void trval(struct TreeNode* root,int *num){
    if(root==NULL)return;
    *num+=1;
    trval(root->left,num);
    trval(root->right,num);
}
int countNodes(struct TreeNode* root) {
    int ans=0;
    trval(root,&ans);
    return ans;
}

思路二：下面介绍另一种方法。首先判断该完全二叉树是否为满二叉树：

  • 若为满二叉树，那么节点的个数为2^n-1,其中n为二叉树高度。
  • 若不为满二叉树，那么分别计算左右子树的节点数，然后相加。

那么，如何判断二叉树呢？

只需要判断根-左孩子-左孩子-左孩子…与跟-右孩子-右孩子-右孩子…这两条路径的长度是否相同即可。因为题目已知这是一颗完全二叉树，只要两边的节点存在，中间的节点一定存在。具体见代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int countNodes(struct TreeNode* root) {
    if(root==NULL)return 0;
    //判断是否为满二叉树：是——>节点个数为2^n-1，n为深度
    //                  否——>分别计算左右子树的节点数，并相加
    struct TreeNode* Left=root->left;
    struct TreeNode* Right=root->right;
    int leftdepth=0,rightdepth=0;
    
    while(Left){
        leftdepth++;
        Left=Left->left;
    }
    while(Right){
        rightdepth++;
        Right=Right->right;
    }
    if(leftdepth==rightdepth)return (2<<leftdepth)-1;
    return countNodes(root->left)+countNodes(root->right)+1;
}

平衡二叉树

110. 平衡二叉树

思路：用定义，计算每个节点的平衡因子

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int depth(struct TreeNode* root){
    if(root==NULL)return 0;
    return fmax(depth(root->left),depth(root->right))+1;
}
bool isBalanced(struct TreeNode* root) {
    if(root==NULL)return true;
    if(fabs(depth(root->left)-depth(root->right))<=1){
        return isBalanced(root->left)&&isBalanced(root->right);
    }
    else{
        return false;
    }
}

二叉树的所有路径

257. 二叉树的所有路径

思路：按照一种遍历顺序（我使用的是DFS）遍历到叶子节点，存储路径上节点的值。思路很简单，实现有点麻烦。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void getpaths(struct TreeNode* root,char** s,int* stack,int top,int *returnSize){
    if(root==NULL)return;
    if(root->left!=NULL||root->right!=NULL){//当前节点非叶子节点
        stack[top++]=root->val;
        getpaths(root->left,s,stack,top,returnSize);
        getpaths(root->right,s,stack,top,returnSize);
    }
    else{
        char* t=malloc(sizeof(char)*100);
        int len=0;
        for(int i=0;i<top;i++){
            len+=sprintf(t+len,"%d->",stack[i]);
        }
        sprintf(t+len,"%d",root->val);
        s[(*returnSize)++]=t;
    }
}
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char **ans=malloc(sizeof(char*)*100);
    *returnSize=0;
    int stack[100+5];
    getpaths(root,ans,stack,0,returnSize);
    return ans;
}

左叶子之和

404. 左叶子之和

思路：遍历，找到所有左叶子，然后相加。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//判断是否为叶子节点
bool isleaf(struct TreeNode* root){
    if(root==NULL)return false;
    if(root->left==NULL&&root->right==NULL)return true;
    return false;
}
int sumOfLeftLeaves(struct TreeNode* root) {
    if(root==NULL)return 0;
    int sum=0;
    
    if(isleaf(root->left)){//左孩子是叶子
        sum=sum+root->left->val+sumOfLeftLeaves(root->right);
    }
    else{
        sum=sum+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
    return sum;
}

找左下角的值

513. 找树左下角的值

思路一：DFS，找到每个子树左下角的值，并计算子树的高度，若左子树更高，取左子树左下角的值；若右子树更高，取右子树左下角的值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isleaf(struct TreeNode* root){
    if(root==NULL)return false;
    if(root->left==NULL&&root->right==NULL)return true;
    return false;
}
int find(struct TreeNode* root,int* depth){//返回左下的值，并计算深度
    if(root==NULL){
        return 0;//这里随便返回一个值，因为如果传来一个空指针，计算的深度为0，不会选用
                 
    }
    (*depth)++;
    if(isleaf(root)){
        
        return root->val;
    }
    int leftdepth=0;//左子树高度
    int rightdepth=0;//右子树高度
    int findleft=find(root->left,&leftdepth);//左子树的左下角
    int findright=find(root->right,&rightdepth);//左子树的左下角
    if(leftdepth>=rightdepth){
       
        (*depth)+=leftdepth;
         return findleft;
    }
    else {
        (*depth)+=rightdepth;
        return findright;
    } 
    
}
int findBottomLeftValue(struct TreeNode* root) {
    if(isleaf(root)){       
        return root->val;
    }
    int leftdepth=0;//左子树高度
    int rightdepth=0;//右子树高度
    int findleft=find(root->left,&leftdepth);//左子树的左下角
    int findright=find(root->right,&rightdepth);//左子树的左下角
    if(leftdepth>=rightdepth){
        return findleft;
    }
    else return findright; 
}

思路二：既然要取最后一层最左边的值，那么层序遍历也是可以的。这里有个技巧处理，先将左孩子入队，再将左孩子入队，这样最后一个入队的元素就是左下角元素。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int findBottomLeftValue(struct TreeNode* root) {
   int ans=0;
   struct TreeNode* queue[10000];
    int front=0;
    int tail=0;
    if(root==NULL)return 0;
    queue[front++]=root;
    while(front>tail){
        int t=front;
        while(tail<t){
           struct TreeNode* node=queue[tail++];
            if(node->right){
                
                queue[front++]=node->right;
            }
            if(node->left){
               
                queue[front++]=node->left;
            }
            ans=queue[front-1]->val;
        }
    
    }
    return ans;
}

路径总和

112. 路径总和

思路：递归，回溯

image.png

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool hasPathSum(struct TreeNode* root, int targetSum) {
    if(root==NULL)return false;
    if(root->left==NULL&&root->right==NULL){//如果是叶子节点
        return root->val==targetSum;
    }
    return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}

从中序与后序序列构造二叉树

思路：递归

1.由后序遍历的最后一个元素得到根节点
2.再根据中序遍历序列和根节点，将中序遍历序列分为左右子树的中序遍历序列
3.左右子树的个数，将后序遍历序列分为左右子树的后序遍历序列

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//1.由后序遍历的最后一个元素得到根节点
//2.再根据中序遍历序列和根节点，将中序遍历序列分为左右子树的中序遍历序列
//3.左右子树的个数，将后序遍历序列分为左右子树的后序遍历序列

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    if (inorderSize == 0 || postorderSize == 0) return NULL;

    // 创建根节点，值为后序遍历的最后一个元素
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = postorder[postorderSize - 1];
    root->left = NULL;
    root->right = NULL;

    // 在中序遍历中找到根节点的位置
    int index = 0;
    while (index < inorderSize && inorder[index] != root->val) {
        index++;
    }

    // 递归构建左子树
    root->left = buildTree(inorder, index, postorder, index);

    // 递归构建右子树
    root->right = buildTree(inorder + index + 1, inorderSize - index - 1, postorder + index, postorderSize - index - 1);

    return root;
}

最大二叉树

654. 最大二叉树

思路：递归。

和上一题思路差不多，将原序列从中间（本题为最大值）分为三部分，分别作为左孩子，根，右孩子，然后对左右孩子进行相同的操作。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    if(numsSize==0)return NULL;
    int maxval=nums[0],maxindex=0;
    for(int i=0;i<numsSize;i++){//找到最大值，作为根节点
        if(nums[i]>maxval){
            maxval=nums[i];
            maxindex=i;
        }
    }
    struct TreeNode *root=malloc(sizeof(struct TreeNode));
    root->val=maxval;
    root->left=constructMaximumBinaryTree(nums,maxindex);
    root->right=constructMaximumBinaryTree(nums+maxindex+1,numsSize-maxindex-1);
    return root;
}

合并二叉树

617. 合并二叉树

思路：见代码注释。递归。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    //1.若都是NULL，返回NULL(可省略)
    //2.只有一个为NULL，直接返回另一个不为空的树
    //3.两个都不为空时，左子树与左子树，右子树与右子树合并，根的值相加
   
   //1.若都是NULL，返回NULL(可省略)
   if(root1==NULL&&root2==NULL)return NULL; 
    //2.只有一个为NULL，直接返回另一个不为空的树
    if(root1==NULL)return root2;
    if(root2==NULL)return root1;
    //3.两个都不为空时，左子树与左子树，右子树与右子树合并，根的值相加
    struct TreeNode* mergeroot=malloc(sizeof(struct TreeNode));
    mergeroot->val=root1->val+root2->val;
    mergeroot->left=mergeTrees(root1->left,root2->left);
    mergeroot->right=mergeTrees(root1->right,root2->right);
    return mergeroot;
}

二叉搜索树中的搜索

700. 二叉搜索树中的搜索

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 //BST中：左<根<右
 //按照二叉搜索树的规则搜索就好了
struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if(root==NULL)return NULL;
    if(root->val==val)return root;
    else if(root->val<val){
      return  searchBST(root->right,val);
    }
    else return searchBST(root->left,val);
}

验证二叉搜索树

98. 验证二叉搜索树

思路：某年的408真题，当时我还写错了。我当时将问题转化为判断是否每个节点都满足：左<根<右，但其实这样是错误的。

正确做法是利用二叉搜索树的一个特性：中序遍历序列是递增的，我们验证这个就好了。

我是直接把中序遍历序列放入一个数组中，再验证该数组是否严格递增。（这样效率不高，但实现简单）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void inorder(struct TreeNode*root,int *nums,int *len){
    if(root==NULL)return;
    inorder(root->left,nums,len);
    nums[(*len)++]=root->val;
    inorder(root->right,nums,len);
}
bool isValidBST(struct TreeNode* root) {
    int *len=malloc(sizeof(int));
    *len=0;
    int *nums=malloc(sizeof(int)*10005);
    inorder(root,nums,len);
    for(int i=0;i<*len-1;i++){
        if(nums[i]>=nums[i+1])return false;
    }
    return true;
}

还有一种方法是：保存上一次访问的值，当访问某个节点时，可以与上一次访问的值比较，若不大于上一次访问的值，直接访问false；这样在时间与空间效率都更高。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool inorder(struct TreeNode*root,long long *pre){
    if(root==NULL)return true;
    bool res=inorder(root->left,pre);
    if(root->val<=*pre){
        return false;
    }
    *pre=root->val;
    return inorder(root->right,pre)&&res;
}
bool isValidBST(struct TreeNode* root) {
    long long pre=LONG_MIN;
    return inorder(root,&pre);
}

二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差

思路：中序遍历，用min记录结果，用pre记录上一次访问的值，计算本次访问节点的值与pre的差，比较与min之间的大小关系，并更新min

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
long long Abs(long long a){
    if(a>0)return a;
    return 0-a; 
}
void inorder(struct TreeNode* root,long long *pre,long long* min){
    if(root==NULL)return;
    inorder(root->left,pre,min);
    if(Abs(root->val-*pre)<*min)*min=Abs(root->val-*pre);
    *pre=root->val;
    inorder(root->right,pre,min);
}
int getMinimumDifference(struct TreeNode* root) {
    long long *pre=malloc(sizeof(long long));
    *pre=INT_MIN;
    long long *min=malloc(sizeof(long long));
    *min=LONG_MAX;
    inorder(root,pre,min);
    return *min;
}

二叉树中的众数

501. 二叉搜索树中的众数

思路一：哈希表，最简单的思路。遍历一遍二叉树，用哈希表统计

每个数出现的次数，遍历哈希表，找到出现次数最大的数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void inorder(struct TreeNode* root,int *hash){
    if(root==NULL)return;
    inorder(root->left,hash);
    hash[root->val+100000]++;
    inorder(root->right,hash);
}
int* findMode(struct TreeNode* root, int* returnSize) {
    int hash[200005];
    memset(hash,0,sizeof(hash));
    int Maxnum=0;
    inorder(root,hash);
    for(int i=0;i<=200000;i++){
        if(hash[i]>Maxnum)Maxnum=hash[i];
    }
    int *ans=malloc(sizeof(int)*10000);
    *returnSize=0;
    for(int i=0;i<=200000;i++){
        if(hash[i]==Maxnum)ans[(*returnSize)++]=i-100000;
    }
    return ans;
}

思路二：

  1. 利用中序遍历：

    二叉搜索树（BST）的中序遍历结果是一个有序数组，因此可以通过中序遍历统计节点值的频率。

  2. 统计频率：

    使用一个变量Curnum记录当前节点值的连续出现次数。

    使用另一个变量Maxnum记录当前的最大频率。

  3. 更新众数：

    如果Curnum > Maxnum，说明当前节点值的频率更高，更新Maxnum，并重置众数数组。

    如果Curnum == Maxnum，说明当前节点值也是众数，将其加入众数数组。

  4. 两次遍历：

    第一次遍历：确定众数的最大频率（Maxnum）和众数的数量（returnSize）。

    第二次遍历：根据Maxnum和returnSize，将众数存入分配好的数组中。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 中序遍历函数，用于统计节点值的频率并找到众数
void inorder(struct TreeNode* root, struct TreeNode **pre, int *Maxnum, int *Curnum, int* ans, int* returnSize) {
    if (root == NULL) return; // 如果当前节点为空，直接返回

    // 递归遍历左子树
    inorder(root->left, pre, Maxnum, Curnum, ans, returnSize);

    // 处理当前节点
    if (*pre && (*pre)->val == root->val) {
        (*Curnum)++; // 如果当前节点值与前一个节点值相同，增加当前频率
    } else {
        *Curnum = 1; // 否则，重置当前频率为1
    }

    // 更新最大频率和众数数组
    if (*Curnum > *Maxnum) {
        *Maxnum = *Curnum; // 如果当前频率大于最大频率，更新最大频率
        *returnSize = 1;   // 重置众数数组大小为1
    } else if (*Curnum == *Maxnum) {
        if (ans) {
            ans[*returnSize] = root->val; // 如果当前频率等于最大频率，将当前值存入众数数组
        }
        (*returnSize)++; // 增加众数数组大小
    }

    *pre = root; // 更新前一个节点为当前节点

    // 递归遍历右子树
    inorder(root->right, pre, Maxnum, Curnum, ans, returnSize);
}

// 查找众数的主函数
int* findMode(struct TreeNode* root, int* returnSize) {
    int Maxnum = 0; // 最大频率
    int Curnum = 0; // 当前频率
    *returnSize = 0; // 众数数组大小
    struct TreeNode* pre = NULL; // 前一个节点指针

    // 第一次中序遍历：确定最大频率和众数数量
    inorder(root, &pre, &Maxnum, &Curnum, NULL, returnSize);

    // 分配众数数组内存
    int* ans = malloc(sizeof(int) * (*returnSize));
    if (ans == NULL) {
        *returnSize = 0; // 如果内存分配失败，返回空数组
        return NULL;
    }

    // 重置变量
    Curnum = 0;
    *returnSize = 0;
    pre = NULL;

    // 第二次中序遍历：填充众数数组
    inorder(root, &pre, &Maxnum, &Curnum, ans, returnSize);

    return ans; // 返回众数数组
}

二叉树的最近公共祖先

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

思路：

  1. 判断祖先关系：
    • 使用 isanc 函数判断一个节点是否是另一个节点的祖先。
    • 如果 p 是 q 的祖先，直接返回 p；如果 q 是 p 的祖先，直接返回 q。
  2. 递归查找 LCA：
    • 如果 p 和 q 都在左子树中，递归到左子树查找。
    • 如果 p 和 q 都在右子树中，递归到右子树查找。
    • 如果 p 和 q 分别位于左右子树中，则当前节点就是它们的最近公共祖先。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 判断 node 是否是 root 的子孙节点
bool isanc(struct TreeNode* root, struct TreeNode *node) {
    if (root == NULL) return false; // 如果 root 为空，返回 false
    if (root == node) return true;  // 如果 root 就是 node，返回 true
    // 递归检查左子树和右子树
    return isanc(root->left, node) || isanc(root->right, node);
}

// 查找 p 和 q 的最近公共祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL; // 如果当前节点为空，返回 NULL

    // 如果 p 是 q 的祖先，直接返回 p
    if (isanc(p, q)) return p;
    // 如果 q 是 p 的祖先，直接返回 q
    if (isanc(q, p)) return q;

    // 如果 p 和 q 都在左子树中，递归到左子树查找
    if (isanc(root->left, p) && isanc(root->left, q)) {
        return lowestCommonAncestor(root->left, p, q);
    }
    // 如果 p 和 q 都在右子树中，递归到右子树查找
    if (isanc(root->right, p) && isanc(root->right, q)) {
        return lowestCommonAncestor(root->right, p, q);
    }

    // 如果 p 和 q 分别位于左右子树中，则当前节点就是 LCA
    return root;
}

优化：

  1. 递归遍历：
    • 从根节点开始递归遍历树。
    • 如果当前节点是 p 或 q，直接返回当前节点。
  2. 判断左右子树：
    • 递归查找左子树和右子树。
    • 如果 p 和 q 分别在左右子树中，则当前节点就是它们的最近公共祖先。
    • 如果 p 和 q 都在左子树中，返回左子树的结果。
    • 如果 p 和 q 都在右子树中，返回右子树的结果。
  3. 时间复杂度：
    • 每个节点最多被访问一次，时间复杂度为 O(n)，其中 n 是树的节点数。
  4. 空间复杂度：
    • 递归栈的深度为树的高度，空间复杂度为 O(h)，其中 h 是树的高度。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL; // 如果当前节点为空，返回 NULL

    // 如果当前节点是 p 或 q，直接返回当前节点
    if (root == p || root == q) {
        return root;
    }

    // 递归查找左子树和右子树
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 如果 p 和 q 分别在左右子树中，则当前节点是 LCA
    if (left && right) {
        return root;
    }

    // 如果 p 和 q 都在左子树中，返回左子树的结果
    if (left) {
        return left;
    }

    // 如果 p 和 q 都在右子树中，返回右子树的结果
    if (right) {
        return right;
    }

    // 如果 p 和 q 都不在当前子树中，返回 NULL
    return NULL;
}

二叉搜索树的最近公共祖先

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

思路：用上一题的思路也能对。

下面是针对BST的改进

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL; // 如果当前节点为空，返回 NULL

    // 如果当前节点是 p 或 q，直接返回当前节点
    if (root == p || root == q) {
        return root;
    }
    //当前节点大于p，q的值，继续向左子树找
    if(root->val>q->val&&root->val>p->val)
        return lowestCommonAncestor(root->left,p,q);
    //当前节点小于p，q的值，继续向右子树找
    else if(root->val<q->val&&root->val<p->val)
        return lowestCommonAncestor(root->right,p,q);
    //当前节点位于p，q中间，该节点就是p，q的LCA
    else return root;

}

二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作

  • 使用指针 p 遍历树，找到合适的插入位置。
  • 如果 val 小于当前节点值，尝试插入到左子树；否则尝试插入到右子树。
  • 如果当前节点的左子树或右子树为空，直接插入新节点。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    // 创建新节点
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;

    // 如果树为空，直接返回新节点
    if (root == NULL) {
        return node;
    }

    // 使用指针 p 遍历树
    struct TreeNode* p = root;
    while (p) {
        // 如果 val 小于当前节点值，尝试插入到左子树
        if (val < p->val) {
            if (p->left == NULL) {
                p->left = node; // 左子树为空，直接插入
                break;
            } else {
                p = p->left; // 继续遍历左子树
            }
        }
        // 如果 val 大于等于当前节点值，尝试插入到右子树
        else {
            if (p->right == NULL) {
                p->right = node; // 右子树为空，直接插入
                break;
            } else {
                p = p->right; // 继续遍历右子树
            }
        }
    }

    // 返回根节点
    return root;
}

删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) return NULL; // 如果树为空，直接返回 NULL

    // 如果 key 小于当前节点值，递归到左子树删除
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    // 如果 key 大于当前节点值，递归到右子树删除
    else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    }
    // 如果 key 等于当前节点值，删除当前节点
    else {
        // 情况 1：当前节点没有子节点
        if (root->left == NULL && root->right == NULL) {
            free(root); // 释放内存
            return NULL;
        }
        // 情况 2：当前节点只有右子树
        else if (root->left == NULL) {
            struct TreeNode* temp = root->right; // 保存右子树
            free(root); // 释放内存
            return temp; // 返回右子树
        }
        // 情况 3：当前节点只有左子树
        else if (root->right == NULL) {
            struct TreeNode* temp = root->left; // 保存左子树
            free(root); // 释放内存
            return temp; // 返回左子树
        }
        // 情况 4：当前节点有左右子树
        else {
            // 找到右子树中的最小值节点（最左节点）
            struct TreeNode* p = root->right;
            while (p->left) {
                p = p->left;
            }
            // 用最小值节点的值替换当前节点值
            root->val = p->val;
            // 递归删除右子树中的最小值节点
            root->right = deleteNode(root->right, p->val);
        }
    }

    // 返回根节点
    return root;
}

方法二：迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) return NULL; // 如果树为空，直接返回 NULL

    // 如果当前节点是需要删除的节点
    if (root->val == key) {
        // 情况 1：当前节点是叶子节点（没有子节点）
        if (root->left == NULL && root->right == NULL) {
            free(root); // 释放内存
            return NULL; // 返回 NULL
        }
        // 情况 2：当前节点只有左子树
        else if (root->left != NULL && root->right == NULL) {
            struct TreeNode* leftChild = root->left; // 保存左子树
            free(root); // 释放当前节点内存
            return leftChild; // 返回左子树
        }
        // 情况 3：当前节点只有右子树
        else if (root->left == NULL && root->right != NULL) {
            struct TreeNode* rightChild = root->right; // 保存右子树
            free(root); // 释放当前节点内存
            return rightChild; // 返回右子树
        }
        // 情况 4：当前节点有左右子树
        else {
            // 找到左子树中的最大值节点（最右节点）
            struct TreeNode* pre = root; // 记录父节点
            struct TreeNode* p = root->left; // 从左子树开始
            while (p->right != NULL) {
                pre = p;
                p = p->right;
            }

            // 如果最大值节点不是左子树的根节点
            if (pre != root) {
                pre->right = p->left; // 将最大值节点的左子树挂到其父节点的右子树
            } else {
                pre->left = p->left; // 如果最大值节点是左子树的根节点，直接挂到左子树
            }

            // 用最大值节点替换当前节点
            p->left = root->left;
            p->right = root->right;
            free(root); // 释放当前节点内存
            return p; // 返回替换后的节点
        }
    }
    // 如果 key 小于当前节点值，递归到左子树删除
    else if (key < root->val) {
        root->left = deleteNode(root->left, key);
    }
    // 如果 key 大于当前节点值，递归到右子树删除
    else {
        root->right = deleteNode(root->right, key);
    }

    // 返回当前节点
    return root;
}

修剪二叉搜索树

669. 修剪二叉搜索树

思路：递归修剪：

  • 如果当前节点为空，直接返回 NULL。
  • 如果当前节点的值小于 low，说明当前节点及其左子树都不在范围内，直接递归修剪右子树。
  • 如果当前节点的值大于 high，说明当前节点及其右子树都不在范围内，直接递归修剪左子树。
  • 如果当前节点的值在 [low, high] 范围内，递归修剪其左右子树，并返回当前节点。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
    // 如果当前节点为空，直接返回 NULL
    if (root == NULL) return NULL;

    // 如果当前节点的值小于 low，说明当前节点及其左子树都不在范围内
    // 直接递归修剪右子树
    if (root->val < low) {
        return trimBST(root->right, low, high);
    }

    // 如果当前节点的值大于 high，说明当前节点及其右子树都不在范围内
    // 直接递归修剪左子树
    if (root->val > high) {
        return trimBST(root->left, low, high);
    }

    // 如果当前节点的值在 [low, high] 范围内
    // 递归修剪左子树和右子树
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);

    // 返回当前节点
    return root;
}

将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

思路：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;

    // 创建根节点，值为数组的中间元素
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    int mid = numsSize / 2;
    root->val = nums[mid];

    // 递归构建左子树和右子树
    root->left = sortedArrayToBST(nums, mid); // 左子树使用数组的左半部分
    root->right = sortedArrayToBST(nums + mid + 1, numsSize - mid - 1); // 右子树使用数组的右半部分

    return root;
}

把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

思路：累加树的新节点的值等于原树中值大于等于原值的值之和，可以利用二叉搜索树中序遍历有序这个性质，就可以得到所有大于等于该值的所有节点的值。

一般的中序遍历是左-根-右遍历，得到的是升序序列，我们这里可以用右-根-左的顺序遍历，得到的是降序遍历的序列，用sum记录累加和，就可以在遍历时对节点进行修改。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 按照右、根、左的顺序遍历二叉树
void inorder(struct TreeNode* root, int *sum) {
    // 如果当前节点为空，直接返回
    if (root == NULL) return;

    // 1. 先遍历右子树（较大的值）
    inorder(root->right, sum);

    // 2. 处理当前节点
    *sum += root->val;  // 将当前节点的值累加到 sum 中
    root->val = *sum;   // 更新当前节点的值为累加后的 sum

    // 3. 最后遍历左子树（较小的值）
    inorder(root->left, sum);
}

// 将二叉搜索树转换为累加树
struct TreeNode* convertBST(struct TreeNode* root) {
    int sum = 0;  // 初始化累加和为 0
    inorder(root, &sum);  // 调用辅助函数进行遍历和累加
    return root;  // 返回转换后的树
}

至此，二叉树部分告一段落！


http://www.kler.cn/a/520997.html

相关文章：

  • location的使用规则
  • C语言学习强化
  • 一文讲解Java中的接口和抽象类
  • 保定学院寒假第一次训练赛题解
  • C语言初阶牛客网刷题—— HJ34 图片整理【难度：中等】
  • 01机器学习入门
  • jQuery阶段总结
  • 数据结构：二叉树—面试题（二）
  • Microsoft Entra ID允许普通用户更新自己的UPN
  • 【Linux】统计文本中每行指定位置出现的字符串的次数
  • 进程控制的学习
  • 微服务学习-Nacos 配置中心实战
  • 在 AMD GPU 上使用 vLLM 的 Triton 推理服务器
  • OpenAI 发布首个 AI 智能体
  • [ Spring ] Spring Cloud Alibaba Aliyun OSS 2025
  • 电梯系统的UML文档11
  • 字节跳动发布UI-TARS，超越GPT-4o和Claude，能接管电脑完成复杂任务
  • 蓝桥杯备考：哈希表和unorderd_set
  • 算法每日双题精讲 —— 二分查找（寻找旋转排序数组中的最小值，点名）
  • ＜ OS 有关 ＞ 阿里云：轻量应用服务器 的使用 ：轻量化 阿里云 vpm 主机