牛客网面试必刷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.判断是不是完全二叉树

题目：

示例：

解题思路

分析一下完全二叉树的性质，叶子节点只能出现在最下层和次下层，所以我们想到可以使用队列辅助进行层次遍历——从上到下遍历所有层，每层从左到右，一旦遇到空节点，就不会再遇到空节点，再遇到就说明不是完全二叉树。

算法流程：

1. 根节点为空，则是完全二叉树，不空，则初始化对列，初始化成员变量empty为false，根节点入队。
2. 元素出队并赋值给 node。
3. node为空，则将 empty 置为 true，node不空，则判断empty是否为true，为true则返回false，即不是完全二叉树，为false则将node左右节点入队（不管是不是空节点）。
4. 回到步骤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 的最近公共祖先，只存在三种情况：

1. o1 ，o2 分别位于root的左右子树上
   
2. o1 = root, 且 o2 位于root的左子树/右子树中
   
3. o2 = root, 且 o1 位于root的左子树/右子树中。

算法流程：

1. 当到达空节点（既叶子节点的子节点）时，直接返回false。
2. 当root等于 o1 或 o2 时，说明root就是最近公共祖先，将节点值赋予成员变量result，返回true。
3. 若不为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！