牛客网面试必刷TOP101之——判断某种二叉树以及寻找最近公共祖先节点
⚓️作者简介：北京某能源高校非科班大四学生。
📚座右铭：“九层之台，起于垒土” 。所以学习技术须脚踏实地。
📖这里推荐一款刷题、模拟面试神器，可助你斩获大厂offer：点我免费刷题、模拟面试
文章目录
- 前言
- 面试必刷题
- 1.判断是不是二叉搜索树
- 2.判断是不是完全二叉树
- 3.判断是不是平衡二叉树
- 4.二叉搜索树的最近公共祖先
- 5.在二叉树中找到两个节点的最近公共祖先
前言
🌏牛客网是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的招聘类网站，更是一个专注于程序员的学习和成长的平台。
在某次浏览博客的过程中，我偶然点进一个链接，注册了牛客账号。一来到牛客首页，我就被其丰富的功能与良好的社区环境所吸引：
进入题库，更是有最新校招试题与专项练习：
在线编程更是有在线调试功能，可大大提高debug效率：
问答题下还有超多牛客用户交流：
🔔总之，牛客是一个专注于程序员的学习和成长的平台，所以我极力推荐大家注册牛客，坚持刷题，充实自己，大厂offer便指日可待。
面试必刷题
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。上一节我们练习了二叉树的层序遍历与二叉树转换为双向链表，这一节来刷几个进阶点的题目：
📚
1.判断是不是二叉搜索树
题目：
示例：
解题思路
二叉搜索树的特性就是中序遍历是递增序。既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断。只不过在过程中我们要求反退出。
算法流程：
- 首先递归到最左，初始化maxLeft与pre。
- 然后往后遍历整棵树，依次连接pre与当前节点，并更新pre。
- 左子树如果不是二叉搜索树返回false。
- 判断当前节点是不是小于前置节点，更新前置节点。
- 最后由右子树的后面节点决定。
C++解题代码：
class Solution {
public:
int pre = INT_MIN;
bool isValidBST(TreeNode* root) {
if(!root) return true;
if(!isValidBST(root->left)) return false;
if(root->val <= pre) return false;
pre = root->val;
if(!isValidBST(root->right)) return false;
return true;
}
};
2.判断是不是完全二叉树
题目：
示例：
解题思路
分析一下完全二叉树的性质，叶子节点只能出现在最下层和次下层，所以我们想到可以使用队列辅助进行层次遍历——从上到下遍历所有层，每层从左到右，一旦遇到空节点，就不会再遇到空节点，再遇到就说明不是完全二叉树。
算法流程：
- 根节点为空，则是完全二叉树，不空，则初始化对列，初始化成员变量empty为false，根节点入队。
- 元素出队并赋值给 node。
- node为空，则将 empty 置为 true，node不空，则判断empty是否为true，为true则返回false，即不是完全二叉树，为false则将node左右节点入队（不管是不是空节点）。
- 回到步骤2。
C++解题代码：
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
// write code here
if(!root)return true;
queue<TreeNode*> q;
q.push(root);
bool Empty = false;
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
if(!node) Empty = true;
else{
if(Empty) return false;
q.push(node->left);
q.push(node->right);
}
}
return true;
}
};
3.判断是不是平衡二叉树
题目：
示例：
解题思路：
拿准平衡二叉树的性质，利用它的性质解题，即高度差大于一就不是平衡二叉树。
算法步骤：
- 根节点为空，则直接返回true。非空则将全局变量res设为true，进行下一步，即调用递归函数。
- 判断该节点是否为空，空则返回0。不空则对其两个子树进行递归，将函数返回结果存于lh与rh。
- 判断lh和rh的差的绝对值是否大于1，大于1则将res设为false，并返回任意值（因为res设为false后就表明它不是完全二叉树了，后面没有将它设为true的操作）。
- 不大于1则表明当前结点满足二叉树的定义，返回当前结点的高度。
C++解题代码
class Solution {
public:
bool res = true;
bool IsBalanced_Solution(TreeNode* pRoot) {
if(!pRoot) return true;
height(pRoot);
return res;
}
private:
int height(TreeNode* node){
if(!node) return 0;
int lh = height(node->left), rh = height(node->right);
if(lh - rh > 1 || lh - rh < -1) {
res = false;
return -1;
}else{
return max(rh, lh) + 1;
}
}
};
4.二叉搜索树的最近公共祖先
题目：
示例：
解题思路：
二叉搜索树的前序遍历序列递增，左节点小于该节点，右节点大于该节点。所以当两个值包含了某个节点的值，那么这个节点就是最近公共祖先。
算法步骤：
进行递归。
- 当前结点值小于 q，p，就在当前结点的左子树寻找最近公共祖先。
- 当前结点值大于 q，p，就在当前结点的右子树寻找最近公共祖先。
- p，q 包含了当前结点值，即 q<=val<=p，或 q>=val>=p，那么公共祖先就是该节点。
C++解题代码
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
// write code here
if (p > root->val && q > root->val) {
return lowestCommonAncestor(root->right, p, q);
} else if (p < root->val && q < root->val) {
return lowestCommonAncestor(root->left, p, q);
}
return root->val;
}
};
5.在二叉树中找到两个节点的最近公共祖先
题目：
示例：
解题思路：
这一题就比上题难多了，因为不能用查找二叉树的性质了。但我们还可以利用递归来解决这个问题。
分析可知，对于节点 o1, o2 的最近公共祖先，只存在三种情况：
- o1 ，o2 分别位于root的左右子树上
- o1 = root, 且 o2 位于root的左子树/右子树中
- o2 = root, 且 o1 位于root的左子树/右子树中。
算法流程：
- 当到达空节点（既叶子节点的子节点）时，直接返回false。
- 当root等于 o1 或 o2 时，说明root就是最近公共祖先，将节点值赋予成员变量result，返回true。
- 若不为1， 2中情况，说明需要继续处理：
对左子树进行递归，返回值记为 a
对右子树进行递归，返回值记位 b- 当a，b都为true时，说明root的就是最近公共祖先，将节点值赋予成员变量result。
- 否则返回 a || b，即将左右子树是否含有两个节点的信息传递给祖先节点。
C++解题代码：
class Solution {
public:
int result = 0;
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
res(root, o1, o2);
return result;
}
bool res(TreeNode* node, int o1, int o2) {
if (!node) return false;
if (node->val == o1 || node->val == o2) {
result = node->val;
return true;
}
bool a = res(node->right, o1, o2);
bool b = res(node->left, o1, o2);
if (a && b) {
result = node->val;
return true;
}
return a||b;
}
};
🥇我希望通过写博客来结束浑浑噩噩的生活，我更希望通过刷题结束人云亦云的思考。刷题不仅仅是刷题，还是我们与自己内心深处的对话。希望我们可以一起在牛客刷题交流，一起收割大厂offer！