大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天在脉脉上看到一位清华毕业的大佬，拿到了省烟草局的offer，本来想拒掉华为的offer，但是华为给申请了特殊涨薪，涨薪后的总包是烟草局的2倍，这下纠结起来了。
拼论区的脉友各抒己见，基本一边倒的选择烟草，有人认为“烟草一世，华为一时”，稳定大于一切，以后就明白了。还有脉友表示犹豫一秒都是对烟草的不尊重。还有比较有才的脉友炫起了文言文：“烟草之泽，三世而斩。华子，也就三年。”果然是自古评论区出人才。如果是你，你会怎么选？
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道华为面试原题「二叉树的最近公共祖先」。
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大 （一个节点也可以是它自己的祖先）。”
举个例子：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路解析
寻找最近公共祖先存在下面三种情况。
节点p为最近公共祖先，这个时候q在p的左子树或右子树中。
节点q为最近公共祖先，这个时候p在q的左子树或右子树中。
节点node为最近公共祖先，这个时候p和q分别在node的左子树和右子树中。
我们可以通过递归来实现上面的三种情况。下面给出c++和python两种代码实现。
c++代码
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//边界条件
if (root == NULL || root == p || root == q) {
return root;
}
//去左子树中寻找最近公共祖先
TreeNode* left = lowestCommonAncestor(root->left, p, q);
//去右子树中寻找最近公共祖先
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//p和q分别位于root的左右子树，说明root为最近公共祖先
if (left && right) {
return root;
}
//p和q均位于左子树中，返回他们的最近公共祖先
if (left) {
return left;
}
//p和q均位于右子树中，返回他们的最近公共祖先
if (right) {
return right;
}
return NULL;
}
};
python代码
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 边界条件
if root is None or root == p or root == q:
return root
# 去左子树中寻找最近公共祖先
left = self.lowestCommonAncestor(root.left, p, q)
# 去右子树中寻找最近公共祖先
right = self.lowestCommonAncestor(root.right, p, q)
# p和q分别位于root的左右子树，说明root为最近公共祖先
if left and right:
return root
# p和q均位于左子树中，返回他们的最近公共祖先
if left:
return left
# p和q均位于右子树中，返回他们的最近公共祖先
if right:
return right
return None
复杂度分析
时间复杂度： 我们需要遍历整个二叉树，所以时间复杂度跟二叉树的节点总数相关。
空间复杂度： 整个过程用到了递归，递归需要用到函数栈，栈的大小跟递归的深度有关，递归的深度跟二叉树的高度有关，所以空间复杂度跟二叉树的高度有关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
