最近一网友发文称：为什么大家本科毕业月薪都是二三十k，而自己只有十几k。实际上这是一种错觉，本科毕业月薪二三十k实际上是很少的，我们在网上经常会看到应届生在各大厂的开奖年薪动辄30多万，40多万，有的甚至更高。这种情况是存在的，但要求也高，比如字节，华为，腾讯，阿里等确实能给到这么高的薪资，但学历基本上都是211，985以上，有的还要求是硕士。在中国211和985录取的比例加起来还不到5%，大部分人是拿不到这么高的薪资的。双非院校的程序员本科毕业月薪十几k不算少（除非有能力进入大厂），所以不要被那行大厂的薪资给迷惑了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第236题：二叉树的最近公共祖先。
问题描述
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
问题分析
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root)
return root;
// 参考二叉树的后序遍历
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null)// 左子树为空，肯定都在右子树上
return right;
if (right == null)// 右子树为空，肯定都在左子树上
return left;
// 左右子树都不为空，一个在左子树一个在右子树，所以root就是他们的最近公共祖先节点。
return root;
}
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr || p == root || q == root)
return root;
// 参考二叉树的后序遍历
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr)// 左子树为空，肯定都在右子树上
return right;
if (right == nullptr)// 右子树为空，肯定都在左子树上
return left;
// 左右子树都不为空，一个在左子树一个在右子树，所以root就是他们的最近公共祖先节点。
return root;
}
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root is None or p == root or q == root:
return root
# 参考二叉树的后序遍历
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left is None: # 左子树为空，肯定都在右子树上
return right
if right is None: # 右子树为空，肯定都在左子树上
return left
# 左右子树都不为空，一个在左子树一个在右子树，所以root就是他们的最近公共祖先节点。
return root
1、人人影视：将二十年字幕文件、字幕软件、网站源代码等全部开源 2、华为加班还是这么恐怖。 3、这 10+ 个开发相关的在线工具，还有人没用过吗？？？ 4、一日一技：Python类型标注的高级用法 5、华为今年薪资，出来了！
点击关注公众号，阅读更多精彩内容
