您现在的位置是:首页 >技术教程 >力扣二叉树专题(六)- 合并二叉树、二叉搜索树中的搜索、验证二叉搜索树、二叉搜索树的最小绝对差、二叉搜索树中的众数、二叉树的最近公共祖先 C++实现 总结网站首页技术教程
力扣二叉树专题(六)- 合并二叉树、二叉搜索树中的搜索、验证二叉搜索树、二叉搜索树的最小绝对差、二叉搜索树中的众数、二叉树的最近公共祖先 C++实现 总结
一、617.合并二叉树
递归法-前序遍历
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//1.递归结束 两个树都遍历结束 到空指针
if(root1==nullptr) return root2;
if(root2==nullptr) return root1;
//2.单次递归 合并数值
root1->val += root2->val;//中
//3.递归
root1->left = mergeTrees(root1->left, root2->left);//左
root1->right = mergeTrees(root1->right, root2->right);//右
return root1;
}
};
二、700. 二叉搜索树中的搜索
二叉搜索树是一个有序树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉搜索树
class Solution {
public:
//递归法
TreeNode* searchBST(TreeNode* root, int val) {
//1.根节点为空 找到数值
if(root==nullptr || root->val==val) return root;
//2.单层操作 需要接收找到的节点
TreeNode* result = NULL;
if(root->val > val) result = searchBST(root->left, val);
if(root->val < val) result = searchBST(root->right, val);
return result;
}
};
二叉树遍历的迭代法,栈来模拟深度遍历;队列来模拟广度遍历。对于一般二叉树,递归过程中还有回溯的过程,例如走一个左方向的分支走到头了,那么要调头,在走右分支。
对于二叉搜索树,因为二叉搜索树的节点有序性,可以不使用辅助栈或者队列就可以写出迭代法。二叉搜索树,不需要回溯的过程,因为节点的有序性就帮我们确定了搜索的方向。
class Solution {
public:
//迭代法
TreeNode* searchBST(TreeNode* root, int val)
{
while(root)
{
if(val < root->val) root = root->left;
else if(val > root->val) root = root->right;
else return root;
}
return nullptr;
}
};
三、98. 验证二叉搜索树
方法1:递归,中序遍历,转成数组,再判断是否有序
class Solution {
public:
//递归法
TreeNode* searchBST(TreeNode* root, int val) {
//1.根节点为空 找到数值
if(root==nullptr || root->val==val) return root;
//2.单层操作 需要接收找到的节点
TreeNode* result = NULL;
if(root->val > val) result = searchBST(root->left, val);
if(root->val < val) result = searchBST(root->right, val);
return result;
}
};
方法2:递归,中序遍历,比较左子树所有节点小于中间节点,右子树所有节点大于中间节点。注意不是,单纯比较左节点小于中间节点,右节点大于中间节点。
class Solution {
public:
long long maxVal = LONG_MIN;
bool isValidBST(TreeNode* root)
{
if(root==NULL) return true;
bool left = isValidBST(root->left);
if(maxVal < root->val) maxVal = root->val;
else return false;
bool right = isValidBST(root->right);
return left&&right;
}
};
四、530. 二叉搜索树的最小绝对差
- 递归,中序遍历,转成有序数组之后找最小差值
class Solution {
public:
vector<int> v;
void traversal(TreeNode* node)
{
if(node==nullptr) return;
traversal(node->left);
v.push_back(node->val);
traversal(node->right);
}
int getMinimumDifference(TreeNode* root) {
v.clear();
traversal(root);
int result = INT_MAX;
for(int i=1;i<v.size();i++)
{
result = min(result, v[i]-v[i-1]);
}
return result;
}
};
- 递归,中序遍历,前后指针找最小差值
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur)
{
if(cur==nullptr) return;
traversal(cur->left);//左
if(pre!=nullptr)//中
{
result = min(result, cur->val - pre->val);
}
pre = cur;//更新
traversal(cur->right);//右
}
public:
int getMinimumDifference(TreeNode* root)
{
traversal(root);
return result;
}
};
3.迭代,中序遍历,栈,双指针
class Solution {
public:
//方法3,迭代,中序遍历,栈,前后指针
int getMinimumDifference(TreeNode* root)
{
stack<TreeNode*> st;
int result = INT_MAX;
TreeNode* cur = root;
TreeNode* pre = NULL;
while(cur!=nullptr || !st.empty())
{
if(cur!=nullptr)//指针来访问节点,访问到最底层
{
st.push(cur);//将访问的节点放进栈
cur = cur->left;//左
}
else
{
cur = st.top();
st.pop();
if(pre!=nullptr)//中
{
result = min(result, cur->val - pre->val);
}
pre = cur;//更新
cur = cur->right;//右
}
}
return result;
}
};
五、501. 二叉搜索树中的众数
一般二叉树统计众数:把这个树都遍历,用map统计频率,key是元素,频率是value。把频率排个序,最后取前面高频的元素的集合。
步骤:
- map统计,遍历树,前中后序都可以
- 把统计的频率(map中的value)排个序,但是C++使用std::map或者std::multimap可以对key排序,但不能对value排序。需要把map转化vector数组,再进行排序。对应vector里面放的也是pair<int, int>类型的数据,第一个int为元素,第二个int为频率。重新一个虚函数,对value按照制定规则排序。
- 取前面高频的元素,vector中已经是存放着按照频率排好序的pair,那么取出前面的高频元素就可以了
有序数组统计众数:从头遍历有序数组的元素出现频率,相邻两个元素作比较,然后输出频率最高的元素
二叉搜索树统计众数:
- 中序遍历树,前后双指针,两个指针进行比较,统计频率。
- 把pre初始化为null,当pre为NULL时候,就知道这是比较的第一个元素了。
- 频率count 等于 maxCount(最大频率),把这个元素加入到结果集(result数组)中
- 如果count 大于 maxCount(最大频率) ,结果集清空,重新更新maxCount,把对应的元素存入结果集中
方法1:递归,中序遍历,前后指针
class Solution {
private:
int maxCount = 0;
int count = 0;
TreeNode* pre = NULL;
vector<int> result;
void searchBST(TreeNode* cur)
{
if(cur==nullptr) return;//递归结束
searchBST(cur->left);//左
//中 统计频率
if(pre==NULL) count = 1;//第一个节点
else if(pre->val==cur->val) count++;
else count = 1;//与前一个节点数值不同
pre = cur;//更新节点
//找到频率最大值,把对应的元素存入结果集中
if(count==maxCount) result.push_back(cur->val);
//如果当前统计的频率值count > 比之前的频率最大值 maxCount 更新maxCount
//要注意此时结果集要清空,因为maxCount对应的元素发生了变化
if(count>maxCount)
{
maxCount = count;//更新最大频率
result.clear();//清空之前的结果集
result.push_back(cur->val);
}
searchBST(cur->right);
return;
}
public:
vector<int> findMode(TreeNode* root) {
//初始化
count = 0;
maxCount = 0;
TreeNode* pre = NULL;
result.clear();
searchBST(root);
return result;
}
};
方法2:迭代,中序遍历,前后指针,栈
class Solution {
public:
vector<int> findMode(TreeNode* root)
{
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = NULL;
int count = 0;
int maxCount = 0;
vector<int> result;
while(cur || !st.empty())
{
if(cur)//指针访问节点,访问到最底层
{
st.push(cur);
cur = cur->left;//左
}
else
{
//中+频率及元素统计
cur = st.top();//访问节点
st.pop();//该节点弹出
//统计频率
if(pre==NULL) count = 1;
else if(pre->val == cur->val) count++;
else count = 1;
//找到频率最大值的元素 存入结果集
if(count == maxCount) result.push_back(cur->val);
//count > maxCount
if(count>maxCount)
{
maxCount = count;
result.clear();//清空,频率最大值更新,对应的元素也要更新
result.push_back(cur->val);//存入当前对应元素
}
pre = cur;//pre更新
cur = cur->right;//右
}
}
return result;
}
};
六、236. 二叉树的最近公共祖先
自底向上查找就可以找到公共祖先了——回溯——后序遍历,根据左右子树的返回值,来处理中节点
- 求最小公共祖先,需要从底向上遍历。二叉树只能通过后序遍历(回溯)实现从底向上的遍历方式。
- 在回溯的过程中,要遍历整棵二叉树。即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
- 如果递归函数有返回值,如何区分要搜索一条边,还是搜索整个树呢?
- 搜索边写法,递归函数返回值不为空的时候,立刻返回
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
- 搜索树写法,利用变量left和right接收返回值,但不能立即返回,还需要做逻辑处理,即left与right逻辑处理完之后才能返回,也就是后序遍历中处理中间节点的逻辑(回溯)
left = 递归函数(root->left); // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理; // 中
对于本题,要搜索整个树,如果在左子树找到了目标节点,也需要在右子树遍历一遍
- 要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果
- 如果left 和 right都不为空,说明此时root就是最近公共节点。这个比较好理解
- 如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然
- 如果left和right都为空,则返回left或者right都是可以的,也就是返回空
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//递归终止条件
if(root == p || root == q || root==NULL) return root;
//单次处理
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
if(left && !right) return left;
else if(!left && right) return right;
else return NULL;
}
};
总结
题一:递归法中,前中后序遍历都可以,两个指针遍历,再合并值。迭代法中,一般一起操作两个树都是使用队列模拟类似层序遍历,同时处理两个树的节点
题二:二叉搜索树首先想到中序遍历,可以转成有序数组。二叉搜索树特性:
- 节点的左子树只包含小于当前节点的数
- 节点的右子树只包含大于当前节点的数
- 所有左子树和右子树自身必须也是二叉搜索树
题三:验证二叉搜索树陷阱
- 不能简单比较左节点小于中间节点,右节点大于中间节点。而是左子树都小于中间节点,右子树都大于中间节点
- 在一个有序序列求最值的时候,不要定义一个全局遍历,然后遍历序列更新全局变量求最值。因为最值可能就是int 或者 longlong的最小值
- 推荐要通过前一个数值(pre)和后一个数值比较(cur),得出最值
题四:二叉搜索树转有序数组,前后指针比较求最小差值,用pre节点记录cur节点的前一个节点
题五:
- 一般二叉树统计众数,map统计,虚函数排序
- 有序数组统计众数,从头遍历,两两比较,统计频率
- 二叉搜索树统计众数,中序遍历,前后指针
题六:
从底向上遍历,回溯,后序遍历
遍历整棵树与遍历局部树(边)写法区别,返回值逻辑操作
怎么把结果传给根节点
其他:
-
平衡二叉搜索树是不是二叉搜索树和平衡二叉树的结合?
是的,是二叉搜索树和平衡二叉树的结合。 -
平衡二叉树与完全二叉树的区别在于底层节点的位置?
是的,完全二叉树底层必须是从左到右连续的,且次底层是满的。 -
堆是完全二叉树和排序的结合,而不是平衡二叉搜索树?
堆是一棵完全二叉树,同时保证父子节点的顺序关系(有序)。 但完全二叉树一定是平衡二叉树,堆的排序是父节点大于子节点,而搜索树是父节点大于左孩子,小于右孩子,所以堆不是平衡二叉搜索树。