代码随想录day8-拓冰建站

1.合并二叉树

力扣题目链接(opens new window)

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

class Solution { public: TreeNode* creat(TreeNode* root1,TreeNode* root2){ if(root1==nullptr&&root2!=nullptr){ return root2; } if(root1!=nullptr&&root2==nullptr){ return root1; } if(root1==nullptr&&root2==nullptr){ return nullptr; } TreeNode* root=new TreeNode(); root->val=root1->val+root2->val; root->left=creat(root1->left,root2->left); root->right=creat(root1->right,root2->right); return root; } TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { return creat(root1,root2); } };

属于二叉树的创建题目

参数为两个节点，返回值是节点类型

终止条件为四种两个节点的存在情况

单次递归逻辑为创建新节点，为新节点赋值，之后创建左右节点。返回当前节点

2.二叉搜索树中的搜索

力扣题目地址(opens new window)

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if(root==nullptr){ return nullptr; } if(root->val==val){ return root; }else if(root->val>val){ return searchBST(root->left,val); }else{ return searchBST(root->right,val); } } };

根据二叉搜索树的特点，直接二分法递归遍历即可。

3.验证二叉搜索树

力扣题目链接(opens new window)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树

class Solution { public: vector<int> res; void travel(TreeNode* root){ if(root==nullptr){ return; } travel(root->left); res.push_back(root->val); travel(root->right); } bool isValidBST(TreeNode* root) { travel(root); for(int i=1;i<res.size();i++){ if(res[i]<=res[i-1]){ return false; } } return true; } };

这里直接使用中序遍历，得到的数组应该是一个升序的数组，即为二叉搜索树

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

力扣题目链接(opens new window)

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

class Solution { public: TreeNode* pre=nullptr; int result=INT_MAX; void dfs(TreeNode* root){ if(root==nullptr){ return ; } dfs(root->left); if(pre){ result=min(result,root->val-pre->val); } pre=root; dfs(root->right); } int getMinimumDifference(TreeNode* root) { dfs(root); return result; } };

最直观的方式是中序遍历，记录在数组中，之后遍历一遍记录最小值，这样内存占比较大，可以直接在遍历二叉树中就记录下最小的差，只需要两个指针就可以了，一个是pre代表前一个节点，root代表当前节点。

5.二叉搜索树中的众数

力扣题目链接(opens new window)

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

class Solution { public: TreeNode* pre=nullptr; int count=0; int maxcount=0; vector<int> result; void searchBST(TreeNode* root){ if(root==nullptr){ return ; } searchBST(root->left);//左 if(pre==nullptr){//中 count=1; }else if(pre->val==root->val){//相等时频率加一 count++; }else{ count=1; } pre=root;//更新上一个节点 if(count==maxcount){ result.push_back(root->val); } if(count>maxcount){ maxcount=count; result.clear(); result.push_back(root->val); } searchBST(root->right);//右 } vector<int> findMode(TreeNode* root) { searchBST(root); return result; } };

一种方式也是直接中序遍历，得到的是有序数组，之后使用map哈希表记录下元素的出现次数，之后得到众数。这种方式的弊端是在获得众数是不能直接堆哈希表进行排序，还需要转换成vector<pair<int,int>>来进行再次的排序，并且由于不只一个最大的频率，还需要再遍历一遍数组。

另一种方式是使用双指针，在进行递归遍历二叉树的时候就可以统计出众数

if(pre==nullptr){//中 count=1; }else if(pre->val==root->val){//相等时频率加一 count++; }else{ count=1; } pre=root;//更新上一个节点 if(count==maxcount){ result.push_back(root->val); } if(count>maxcount){ maxcount=count; result.clear(); result.push_back(root->val); }

使用中序遍历中对节点的处理逻辑，一个指针用于记录上一个节点，当上一个节点为空，说明已经遍历到了最左边，数量记为1，当前节点值与上一个节点值相等的时候，说明元素重复了，数量++，不相等的时候说明遇到新的元素，重新为1。之后更新节点，当当前的数量与最大的数量相等的时候就加入到结果数组中，大于最大数量的时候就更新最大数量，并且要先清除结果数组中的元素（因为有了最大值了），再加入新的元素。

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

力扣题目链接(opens new window)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL||root==p||root==q)return root; TreeNode* left=lowestCommonAncestor(root->left,p,q); TreeNode* right=lowestCommonAncestor(root->right,p,q); if(left!=NULL&&right!=NULL){ return root; }else if(left!=NULL&&right==NULL){ return left; }else { return right; } } };

参数为根节点与两个需要判断的pq节点，返回值为根节点，函数目的是找到p，q的最近公共祖先

终止条件是节点为空，遇到p节点或者遇到q节点，就返回当前节点

定义左右两个节点为当前节点的左右孩子为参数的两个节点的公共祖先，当左右都为空的时候，说明当前节点就是最近的，左节点为空，说明最近公共祖先是右节点，右节点为空，说明是左边节点。

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

力扣题目链接(opens new window)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class Solution { public: TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode* q){ if(root==NULL){ return NULL; } if(root->val>p->val&&root->val>q->val){ TreeNode* left=dfs(root->left,p,q); if(left!=NULL){ return left; } } if(root->val<p->val&&root->val<q->val){ TreeNode* right=dfs(root->right,p,q); if(right!=NULL){ return right; } } return root; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return dfs(root,p,q); } };

与上一题类似，不过可以利用二叉搜索树的特点来进行判断，大抵是使用二分的概念，当前节点的值在这两个节点的中间的时候，说明当前节点就是最近的公共祖先。当大于这两个节点的值的时候就计算出左节点为根节点时的祖先，不为空就直接返回左节点。小于这两个节点的值也是类似。

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

力扣题目链接(opens new window)

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root == nullptr){ return new TreeNode(val); } if(root->val > val){ // 值更小，插入左子树 root->left = insertIntoBST(root->left, val); }else{ // 值更大，插入右子树 root->right = insertIntoBST(root->right, val); } return root; } };

这里是需要返回值的，返回值就是根节点，函数目的是以当前节点为根节点插入节点，并且返回根节点

终止条件是节点为空，返回并创建目标值节点

与当前节点比较大小，比当前节点值大就插入到右子树中，以右子树为根节点进行递归插入，比当前节点值小也是类似的逻辑。

最后返回根节点。

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

力扣题目链接(opens new window)

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；如果找到了，删除它。说明：要求算法时间复杂度为 $O(h)$，h 为树的高度。

class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==nullptr){ return root; } if(key==root->val){ if(!root->left&&!root->right){ delete root; return nullptr; }else if(root->left&&!root->right){ TreeNode* node=root->left; delete root; return node; }else if(root->right&&!root->left){ TreeNode* node=root->right; delete root; return node; }else { TreeNode* cur=root->right; while(cur->left!=nullptr){ cur=cur->left; } cur->left=root->left; TreeNode* tmp=root; root=root->right; delete tmp; return root; } } if(root->val>key){ root->left=deleteNode(root->left,key); } if(root->val<key){ root->right=deleteNode(root->right,key); } return root; } };

函数目的是删除以当前节点为根节点时的指定元素节点

这里需要删除节点，就需要修改树的结构了，

遇到节点时需要删除，还需要分情况讨论

1.是叶子节点，直接删除，返回空

2.左节点存在右节点不存在，删除节点，返回左子树

3.左节点不存在右节点存在，删除节点，返回右子树

4.左右节点都存在，需要把左子树放在右子树的最左下角，循环向下遍历到右子树的左节点，直到叶子节点，把左子树放在叶子节点下，然后删除节点，返回右子树。

没遇到节点就需要递归遍历了，大于当前节点就递归右子树，当前节点右节点为以右节点为根节点删除元素的返回值。小于当前节点就递归左子树。

最后返回根节点。

10.修建二叉搜索树

力扣题目链接(opens new window)

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(root==nullptr) return nullptr; if(root->val>high){ return trimBST(root->left,low,high); } if(root->val<low){ return trimBST(root->right,low,high); } root->left=trimBST(root->left,low,high); root->right=trimBST(root->right,low,high); return root; } };

这里也是需要递归的，函数目的是修剪以当前节点为根节点时的树

终止条件是遇到空节点就返回空

当节点不在修剪范围的时候，就直接返回对应一半的修剪的树

节点在修剪范围内的时候，左节点返回值为以左节点为根节点的修剪过的子树，右节点类似

最后返回根节点。

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

力扣题目链接(opens new window)

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

class Solution { public: TreeNode* creatBst(vector<int>& nums,int left,int right){//创建left到right的子树 if(left>right){ return nullptr; } int mid=left+((right-left)/2);//因为要平衡，所以选择中间元素 TreeNode* node=new TreeNode(nums[mid]); node->left=creatBst(nums,left,mid-1); node->right=creatBst(nums,mid+1,right); return node; } TreeNode* sortedArrayToBST(vector<int>& nums) { return creatBst(nums,0,nums.size()-1); } };

这里需要构建的是平衡二叉搜索树，高度差有限制

所以选择根节点就需要选择数组中间的元素，之后划分两端长度进行再次构建节点。

使用的是左闭右闭的区间，参数是数组，左右两个区间的索引。

12.二叉搜索树转换为累加树

力扣题目链接(opens new window)

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。

class Solution { public: int num=0; TreeNode* convertBST(TreeNode* root) {//反向中序遍历 if(root==nullptr) return nullptr; root->right=convertBST(root->right); root->val=root->val+num; num=root->val; root->left=convertBST(root->left); return root; } };

这里直接使用中序反向遍历就可以了，先便利右节点到叶子节点，之后更新节点的值，再更新num的值，之后遍历左节点。