二叉樹(shù)的最近公共祖先該怎么理解

二叉樹(shù)的最近公共祖先該怎么理解，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

題目：給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

三種情況討論：

如果p和q分別是root的左右節(jié)點(diǎn)，那么root就是我們要找的最近公共祖先
如果p和q都是root的左節(jié)點(diǎn)，那么返回lowestCommonAncestor(root.left,p,q)
如果p和q都是root的右節(jié)點(diǎn)，那么返回lowestCommonAncestor(root.right,p,q)
 

class   Solution {

      public   TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

          if  (root == null)   return   root;

          if  (p == root || q == root)   return   root;

        TreeNode rleft = lowestCommonAncestor(root.left, p, q);

        TreeNode rright = lowestCommonAncestor(root.right, p , q);

          if  (rleft == null)   return   rright;

          if  (rright == null)   return   rleft;

          return   root;   // 此時(shí)是 p 和 q 節(jié)點(diǎn)再root節(jié)點(diǎn)的 左右兩邊

    }

}

關(guān)于二叉樹(shù)的最近公共祖先該怎么理解問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。