# 0236. 二叉樹的最近公共祖先 ## 題目地址(236. 二叉樹的最近公共祖先) <https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。 百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。” 例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4] ``` ```  ``` <pre class="calibre18">``` 示例 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。因為根據定義最近公共祖先節點可以為節點本身。 說明: 所有節點的值都是唯一的。 p、q 為不同節點且均存在于給定的二叉樹中。 ``` ``` ## 前置知識 - 遞歸 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目是求解二叉樹中，兩個給定節點的最近的公共祖先。是一道非常經典的二叉樹題目。 我們之前說過樹是一種遞歸的數據結構，因此使用遞歸方法解決二叉樹問題從寫法上來看是最簡單的，這道題目也不例外。 用遞歸的思路去思考樹是一種非常重要的能力。 如果大家這樣去思考的話，問題就會得到簡化，我們的目標就是分別在左右子樹進行查找p和q。 如果p沒有在左子樹，那么它一定在右子樹（題目限定p一定在樹中）， 反之亦然。 對于具體的代碼而言就是，我們假設這個樹就一個結構，然后嘗試去解決，然后在適當地方去遞歸自身即可。 如下圖所示：  我們來看下核心代碼： ``` <pre class="calibre18">``` <span class="hljs-title">// 如果我們找到了p，直接進行返回，那如果下面就是q呢？ 其實這沒有影響，但是還是要多考慮一下</span> <span class="hljs-keyword">if</span> (!root || root === p || root === q) <span class="hljs-keyword">return</span> root; <span class="hljs-keyword">const</span> left = lowestCommonAncestor(root.left, p, q); <span class="hljs-title">// 去左邊找，我們期望返回找到的節點</span> <span class="hljs-keyword">const</span> right = lowestCommonAncestor(root.right, p, q);<span class="hljs-title">// 去右邊找，我們期望返回找到的節點</span> <span class="hljs-keyword">if</span> (!left) <span class="hljs-keyword">return</span> right; <span class="hljs-title">// 左子樹找不到，返回右子樹</span> <span class="hljs-keyword">if</span> (!right) <span class="hljs-keyword">return</span> left; <span class="hljs-title">// 右子樹找不到，返回左子樹</span> <span class="hljs-keyword">return</span> root; <span class="hljs-title">// 左右子樹分別有一個，則返回root</span> ``` ``` > 如果沒有明白的話，請多花時間消化一下 ## 關鍵點解析 - 用遞歸的思路去思考樹 ## 代碼 代碼支持： JavaScript， Python3 - JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */</span> <span class="hljs-keyword">var</span> lowestCommonAncestor = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root, p, q</span>) </span>{ <span class="hljs-keyword">if</span> (!root || root === p || root === q) <span class="hljs-keyword">return</span> root; <span class="hljs-keyword">const</span> left = lowestCommonAncestor(root.left, p, q); <span class="hljs-keyword">const</span> right = lowestCommonAncestor(root.right, p, q); <span class="hljs-keyword">if</span> (!left) <span class="hljs-keyword">return</span> right; <span class="hljs-title">// 左子樹找不到，返回右子樹</span> <span class="hljs-keyword">if</span> (!right) <span class="hljs-keyword">return</span> left; <span class="hljs-title">// 右子樹找不到，返回左子樹</span> <span class="hljs-keyword">return</span> root; <span class="hljs-title">// 左右子樹分別有一個，則返回root</span> }; ``` ``` - Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for a binary tree node.</span> <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">lowestCommonAncestor</span><span class="hljs-params">(self, root: <span class="hljs-string">'TreeNode'</span>, p: <span class="hljs-string">'TreeNode'</span>, q: <span class="hljs-string">'TreeNode'</span>)</span> -> 'TreeNode':</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root <span class="hljs-keyword">or</span> root == p <span class="hljs-keyword">or</span> root == q: <span class="hljs-keyword">return</span> root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> left: <span class="hljs-keyword">return</span> right <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> right: <span class="hljs-keyword">return</span> left <span class="hljs-keyword">else</span>: <span class="hljs-keyword">return</span> root ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 擴展 如果遞歸的結束條件改為`if (!root || root.left === p || root.right === q) return root;` 代表的是什么意思，對結果有什么樣的影響？ 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。