圖解 | LeetCode #235 二叉搜索樹的最近公共祖先

????關注后回復 “進群” ，拉你進程序員交流群????

作者丨微木

來源丨編程狂想曲

你好，我是微木。

今天分享的內容是LeetCode中235.二叉搜索樹的最近公共祖先 簡單 這個題目。

題目描述：

給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/span>

示例:

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

輸出: 6 

解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。

思路分析
   

    二叉搜索樹的主要性質如下圖：
   
   

    
   
   

    根據題目描述，可以確定兩個節(jié)點p和q，一定在二叉搜索樹中。那么，相比較于根節(jié)點root而言，這兩個節(jié)點有如下幾種情況：
   
   

    1.p和q，一個在root的左子樹，一個在root的右子樹
   
   

    
   
   

    對于這種情況，p和q的最近公共祖先就是根節(jié)點root。
   
    

     2.p和q，都在root的左子樹
    
    

     
    
   

    對于這種情況，p和q的公共祖先，需要在左子樹查找。就節(jié)點p=3和節(jié)點q=9來說，它們的最近公共祖先是節(jié)點6。
   
     

      3.p和q，都在root的右子樹
     
     

      
     
   

    對于這種情況，p和q的公共祖先需要在根節(jié)點root的右子樹查找。就節(jié)點15和27而言，它們的最近公共祖先是節(jié)點20。
   
   

    4.p和q，其中一個節(jié)點就是根節(jié)點
   
   

    
   
   

    對于這種情況，根據公共祖先的定義，與根節(jié)點相同的節(jié)點就是它們的最近公共祖先。這里，節(jié)點p和節(jié)點q的最近公共祖先是根節(jié)點root，也是節(jié)點p。
   
   

    根據上述四種情況的分析，總結來說就是：
   
   

    當節(jié)點p和節(jié)點q都在左子樹時，即都小于根節(jié)點root時，需要在root的左子樹查找其最近公共祖先；
    

   
   

    當節(jié)點p和節(jié)點q都在右子樹時，即都大于根節(jié)點root時，需要在root的右子樹查找其最近公共祖先；
   
   

    當節(jié)點p和節(jié)點q一個在根節(jié)點root的左子樹，一個在其右子樹，或者其中一個節(jié)點和根節(jié)點相同時，root就是其最近公共祖先。
   
   

    至此，根據二叉搜索樹的天然遞歸屬性，代碼實現如下：
   
   

    
   

方法lowestCommonAncestor的用就是給定根節(jié)點root，然后找到節(jié)點p和q的最近公共祖先返回。因此，該方法就是遞歸函數。

那么，當需要在左子樹或右子樹中尋找節(jié)點p和節(jié)點q的最近公共祖先時，直接調用該方法就可以。

-End-

最近有一些小伙伴，讓我?guī)兔φ乙恍?nbsp;面試題 資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來，可以說是程序員面試必備！所有資料都整理到網盤了，歡迎下載！

點擊??卡片，關注后回復【面試題】即可獲取

在看點這里好文分享給更多人↓↓