国企也要搞末位淘汰了。。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

据新华网，中国新闻网，中国青年网等报道，国务院国资委在国有企业改革会上表示，到2025年，国有企业必须普遍推行末等调整和不胜任退出制度。要清晰界定“退出”标准，用好绩效考核结果，进一步规范退出的情形，不能用违法违纪、到龄退休、主动离职等替代业绩考核不合格的“退出”。

我觉得这个决定特别好，在这个人浮于事的时代，对于那些尸位素餐，敷衍塞责的人员一定要给与彻底清除，把机会让给需要的人。除了国企以外，我觉得公务员，教师，等行业也可以效仿。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第235题：二叉搜索树的最近公共祖先。

问题描述

来源：LeetCode第235题

难度：中等

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。一个节点也可以是它自己的祖先。

示例1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。

• 所有节点的值都是唯一的。

• p、q 为不同节点且均存在于给定的二叉搜索树中。

问题分析

这题说的是在 二叉搜索树 中找到两个节点的最近公共祖先节点，注意是 二叉搜索树 。

如果这两个节点都比根节点小，那么这两个节点肯定都在根节点的左子树上，它俩的最近公共祖先节点肯定也在左子树上，只需要往根节点的左子树查找即可，因为题中说了，一个节点也是它自己的祖先。

如果这两个节点都比根节点大，那么这两个节点肯定都在根节点的右子树上，它俩的最近公共祖先节点肯定也在右子树上，只需要往根节点的右子树查找即可。

如果这两个节点一个比根节点小一个比根节点大，也就是说在根节点的两边，那么根节点就是这两个节点的最近公共祖先节点。

要判断这两个节点是否是在根节点的两边还是在同一边，只需要用根节点与它俩的差值相乘即可，如果 为负的说明在两边，否则在同一边 。

JAVA：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // p,q位于root一侧，这里要注意计算的时候转成long类型，防止溢出。
    while (((long) root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    // p,q位于root两侧
    return root;
}

C++：

public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        // p,q位于root一侧，这里要注意计算的时候转成long类型，防止溢出。
        while ((root->val * 1L - p->val) * (root->val - q->val) > 0)
            root = p->val < root->val ? root->left : root->right;
        // p,q位于root两侧
        return root;
    }

Python：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # p,q位于root一侧，这里要注意计算的时候转成long类型，防止溢出。
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = root.left if p.val < root.val else root.right
    # p,q位于root两侧
    return root

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。