精品推薦：

《征服數(shù)據(jù)結(jié)構(gòu)》專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

《經(jīng)典圖論算法》專欄：50多種經(jīng)典圖論算法全部掌握

最近一網(wǎng)友發(fā)文稱：為什么大家本科畢業(yè)月薪都是二三十k，而自己只有十幾k。實(shí)際上這是一種錯(cuò)覺，本科畢業(yè)月薪二三十k實(shí)際上是很少的，我們?cè)诰W(wǎng)上經(jīng)常會(huì)看到應(yīng)屆生在各大廠的開獎(jiǎng)年薪動(dòng)輒30多萬，40多萬，有的甚至更高。這種情況是存在的，但要求也高，比如字節(jié)，華為，騰訊，阿里等確實(shí)能給到這么高的薪資，但學(xué)歷基本上都是211，985以上，有的還要求是碩士。在中國(guó)211和985錄取的比例加起來還不到5%，大部分人是拿不到這么高的薪資的。雙非院校的程序員本科畢業(yè)月薪十幾k不算少（除非有能力進(jìn)入大廠），所以不要被那行大廠的薪資給迷惑了。

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

來看下今天的算法題，這題是LeetCode的第236題：二叉樹的最近公共祖先。

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

輸出：3

解釋：節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3 。

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

輸出：5

解釋：節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5 。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。

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;
 // 左右子樹都不為空，一個(gè)在左子樹一個(gè)在右子樹，所以root就是他們的最近公共祖先節(jié)點(diǎn)。
 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;
  // 左右子樹都不為空，一個(gè)在左子樹一個(gè)在右子樹，所以root就是他們的最近公共祖先節(jié)點(diǎn)。
  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
 # 左右子樹都不為空，一個(gè)在左子樹一個(gè)在右子樹，所以root就是他們的最近公共祖先節(jié)點(diǎn)。
 return root