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

文章目录

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

前言

代码随想录系列也写了好几期了，我写代码随想录的题目主要是为了准备机试，这也是为什么我只用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 为空，返回 falseif (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 的祖先，直接返回 pif (isanc(p, q)) return p;// 如果 q 是 p 的祖先，直接返回 qif (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 分别位于左右子树中，则当前节点就是 LCAreturn 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 分别在左右子树中，则当前节点是 LCAif (left && right) {return root;}// 如果 p 和 q 都在左子树中，返回左子树的结果if (left) {return left;}// 如果 p 和 q 都在右子树中，返回右子树的结果if (right) {return right;}// 如果 p 和 q 都不在当前子树中，返回 NULLreturn 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的LCAelse 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) {// 如果当前节点为空，直接返回 NULLif (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;  // 初始化累加和为 0inorder(root, &sum);  // 调用辅助函数进行遍历和累加return root;  // 返回转换后的树
}

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/8072.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

深入剖析 Adam 优化器：原理、优势与应用

深入剖析 Adam 优化器：原理、优势与应用

在深度学习领域&#xff0c;优化器的选择对模型的训练效率和性能起着决定性作用。Adam优化器作为一种自适应优化算法&#xff0c;凭借其根据历史梯度信息动态调整学习率的特性&#xff0c;备受研究者和工程师的青睐。它巧妙融合了RMSProp和Momentum两种优化算法的理念&#xff…
阅读更多...
Mybatis入门

Mybatis入门

Mybatis入门 一、mybatis的快速入门 1、创建springboot项目 直接选择必须的依赖&#xff1a;MyBatis Framework和MySQL Driver在项目下创建pojo包&#xff0c;用来存放数据库表对应的实体类 2、配置连接信息 在springboot项目的配置文件中application.properties写入一下信…
阅读更多...
消息队列篇--通信协议篇--MQTT（通配式主题，消息服务质量Qos，EMQX的Broker，MqttClient示例，MQTT报文等）

消息队列篇--通信协议篇--MQTT（通配式主题，消息服务质量Qos，EMQX的Broker，MqttClient示例，MQTT报文等）

MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;是一种轻量级的消息协议。它基于发布/订阅模式&#xff0c;专为低带宽、高延迟或不可靠网络设计。它主要用于物联网&#xff08;IoT&#xff09;设备之间的通信&#xff0c;但也广泛应用于其他需要高效消息传递…
阅读更多...
dmfldr实战

dmfldr实战

dmfldr实战 本文使用达梦的快速装载工具&#xff0c;对测试表进行数据导入导出。 新建测试表 create table “BENCHMARK”.“TEST_FLDR” ( “uid” INTEGER identity(1, 1) not null , “name” VARCHAR(24), “begin_date” TIMESTAMP(0), “amount” DECIMAL(6, 2), prim…
阅读更多...
基于OSAL的嵌入式裸机事件驱动框架——消息队列osal_msg

基于OSAL的嵌入式裸机事件驱动框架——消息队列osal_msg

参考B站up主【架构分析】嵌入式祼机事件驱动框架 感谢大佬分享 消息队列 消息分为hdr和bdy&#xff0c;把消息的头dhr和内容bdy做了一个分离的设计 dhr包括指向下一个消息的指针next&#xff0c;len在创建消息的时候使用&#xff0c;dest_id即目标任务&#xff0c;将消息和任务…
阅读更多...
关于MySQL InnoDB存储引擎的一些认识

关于MySQL InnoDB存储引擎的一些认识

文章目录 一、存储引擎1.MySQL中执行一条SQL语句的过程是怎样的&#xff1f;1.1 MySQL的存储引擎有哪些&#xff1f;1.2 MyIsam和InnoDB有什么区别&#xff1f; 2.MySQL表的结构是什么&#xff1f;2.1 行结构是什么样呢&#xff1f;2.1.1 NULL列表&#xff1f;2.1.2 char和varc…
阅读更多...
单相可控整流电路——单相桥式全控整流电路

单相可控整流电路——单相桥式全控整流电路

以下是关于单相桥式整流电路的介绍&#xff1a; 电路构成&#xff08;带阻性负载的工作情况&#xff09; - 二极管&#xff1a;是电路0的核心元件&#xff0c;通常采用四个同型号或根据需求选择不同型号的二极管&#xff0c;如1N4001、1N4007等&#xff0c;如图Vt1和Vt4是一对…
阅读更多...
Linux（Centos、Ubuntu) 系统安装jenkins服务

Linux（Centos、Ubuntu) 系统安装jenkins服务

该文章手把手演示在Linux系统下如何安装jenkins服务、并自定义jenkins数据文件位置、以及jenkins如何设置国内镜像源加速&#xff0c;解决插件下载失败问题 安装方式&#xff1a;war包安装 阿里云提供的war下载源地址&#xff1a;https://mirrors.aliyun.com/jenkins/war/?s…
阅读更多...
力扣算法题——11.盛最多水的容器

力扣算法题——11.盛最多水的容器

目录 &#x1f495;1.题目 &#x1f495;2.解析思路 本题思路总览 借助双指针探索规律 从规律到代码实现的转化 双指针的具体实现 代码整体流程 &#x1f495;3.代码实现 &#x1f495;4.完结 二十七步也能走完逆流河吗 &#x1f495;1.题目 &#x1f495;2.解析思路…
阅读更多...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】 1.3 广播机制：维度自动扩展的黑魔法

【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】 1.3 广播机制：维度自动扩展的黑魔法

1.3 《广播机制&#xff1a;维度自动扩展的黑魔法》 前言 NumPy 的广播机制是 Python 科学计算中最强大的工具之一&#xff0c;它允许不同形状的数组进行运算&#xff0c;而无需显式地扩展数组的维度。这一机制在实际编程中非常有用&#xff0c;但初学者往往对其感到困惑。在…
阅读更多...
Semantic Kernel - Kernel理解

Semantic Kernel - Kernel理解

目录 一、关于Kernel 二、案例实战 三、运行截图 一、关于Kernel 微软的 Semantic Kernel 项目中，Semantic Kernel 是一个工具框架，旨在使得开发人员能够更容易地将大语言模型（如GPT）集成到不同的应用中。它通过提供一组接口、任务模板和集成模块，使开发者能够轻松地设计…
阅读更多...
【MySQL】--- 复合查询 内外连接

【MySQL】--- 复合查询 内外连接

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; MySQL &#x1f3e0; 基本查询回顾 假设有以下表结构&#xff1a; 查询工资高于500或岗位为MANAGER的雇员&#xff0c;同时还要满足他们的姓名首字母为…
阅读更多...
Qt Designer and Python: Build Your GUI

Qt Designer and Python: Build Your GUI

1.install pyside6 2.pyside6-designer.exe 发送到桌面快捷方式 在Python安装的所在 Scripts 文件夹下找到此文件。如C:\Program Files\Python312\Scripts 3. 打开pyside6-designer 设计UI 4.保存为simple.ui 文件&#xff0c;再转成py文件 用代码执行 pyside6-uic.exe simpl…
阅读更多...
openlayer getLayerById 根据id获取layer图层

openlayer getLayerById 根据id获取layer图层

背景&#xff1a; 在项目中使用getLayerById获取图层&#xff0c;这个getLayerById()方法不是openlayer官方文档自带的&#xff0c;而是自己封装的一个方法&#xff0c;这个封装的方法的思路是&#xff1a;遍历所有的layer&#xff0c;根据唯一标识【可能是id&#xff0c;也可能…
阅读更多...
Qt 控件与布局管理

Qt 控件与布局管理

1. Qt 控件的父子继承关系 在 Qt 中&#xff0c;继承自 QWidget 的类&#xff0c;通常会在构造函数中接收一个 parent 参数。 这个参数用于指定当前空间的父控件&#xff0c;从而建立控件间的父子关系。 当一个控件被设置为另一控件的子控件时&#xff0c;它会自动成为该父控…
阅读更多...
SOME/IP--协议英文原文讲解1

SOME/IP--协议英文原文讲解1

前言 SOME/IP协议越来越多的用于汽车电子行业中&#xff0c;关于协议详细完全的中文资料却没有&#xff0c;所以我将结合工作经验并对照英文原版协议做一系列的文章。基本分三大块&#xff1a; 1. SOME/IP协议讲解 2. SOME/IP-SD协议讲解 3. python/C举例调试讲解 一、SOM…
阅读更多...
Ansible自动化运维实战--script、unarchive和shell模块（6/8）

Ansible自动化运维实战--script、unarchive和shell模块（6/8）

文章目录 一、script模块1.1、功能1.2、常用参数1.3、举例 二、unarchive模块2.1、功能2.2、常用参数2.3、举例 三、shell模块3.1、功能3.2、常用参数3.3、举例 一、script模块 1.1、功能 Ansible 的 script 模块允许你在远程主机上运行本地的脚本文件&#xff0c;其提供了一…
阅读更多...
【模型】RNN模型详解

【模型】RNN模型详解

1. 模型架构 RNN&#xff08;Recurrent Neural Network&#xff09;是一种具有循环结构的神经网络&#xff0c;它能够处理序列数据。与传统的前馈神经网络不同&#xff0c;RNN通过将当前时刻的输出与前一时刻的状态&#xff08;或隐藏层&#xff09;作为输入传递到下一个时刻&…
阅读更多...
《FreqMamba: 从频率角度审视图像去雨问题》学习笔记

《FreqMamba: 从频率角度审视图像去雨问题》学习笔记

paper&#xff1a;FreqMamba: Viewing Mamba from a Frequency Perspective for Image Deraining GitHub&#xff1a;GitHub - aSleepyTree/FreqMamba 目录 摘要 1、介绍 2、相关工作 2.1 图像去雨 2.2 频率分析 2.3 状态空间模型 3、方法 3.1 动机 3.2 预备知识 3…
阅读更多...
iic、spi以及uart

iic、spi以及uart

何为总线&#xff1f; 连接多个部件的信息传输线&#xff0c;是部件共享的传输介质 总线的作用&#xff1f; 实现数据传输&#xff0c;即模块之间的通信 总线如何分类&#xff1f; 根据总线连接的外设属于内部外设还是外部外设将总线可以分为片内总线和片外总线 可分为数…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023