<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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] ``` ``` ![](https://img.kancloud.cn/20/6e/206e04a75ce0958831ffe28f5fcad614_200x190.jpg) ``` <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一定在樹中), 反之亦然。 對于具體的代碼而言就是,我們假設這個樹就一個結構,然后嘗試去解決,然后在適當地方去遞歸自身即可。 如下圖所示: ![](https://img.kancloud.cn/1c/aa/1caac921f1c764cb4205c22e9492b41c_828x378.jpg) 我們來看下核心代碼: ``` <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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看