專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

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

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

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

問題描述

來源：LeetCode第236題

難度：中等

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先 。最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

示例1：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出：3 解釋：節點 5 和節點 1 的最近公共祖先是節點 3 。

示例2：

輸入：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 均存在于給定的二叉樹中。

問題分析

這題讓找出兩個節點的最近公共節點，有兩種解決方式，一種是從兩個要查找的節點到根節點上的路徑都連接起來，那么這兩條路徑就相當于兩個鏈表了，這題就變成了查找兩個鏈表的第一個公共節點了。

怎么連接呢 ？ 我們可以 遍歷這棵二叉樹，然后使用一個map記錄 所遍歷節點的父節點，然后在根據當前節點一直往上查找父節點，一直到根節點，這種方式比較簡單，我們再來看另一種方式 。

查找兩個節點的最近公共節點，也就是從下往上找，我們知道二叉樹都是從上往下遍歷的，沒法從下往上遍歷。也就是說如果知道一個節點，肯定能找到它的子節點，但是我們沒法找到它的父節點。

我們這里再來回顧一下遞歸，對于一棵二叉樹來說因為是從根節點開始的，當 遞歸往回走的時候不就是相當于從下往上遍歷嗎 ，所以這題我們可以參考二叉樹的后序遍歷來寫。

1，如果兩個節點都在左子樹上，就返回左子樹上的結果。

2，如果兩個節點都在右子樹上，就返回右子樹上的結果。

3， 如果兩個節點分別在兩棵子樹上 ， 說明當前節點就是它倆的 最近公共祖先節點，直接返回當前節點即可。

JAVA：

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; }

C++：

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;     }

Python：

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

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。