在Java中以遞歸方式遞歸的最低公共祖先

我在leetcode中發現了Java中最低公共祖先問題的解決方案。問題另外說明的是，找到以根爲根的BST找到p和q的最低共同祖先。這是我的代碼。在Java中以遞歸方式遞歸的最低公共祖先

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
     if(root == null || root == p || root == q) return root; 
     TreeNode left = lowestCommonAncestor(root.left, p, q); 
     TreeNode right = lowestCommonAncestor(root.right, p, q); 
     return left != null && right != null ? root : left == null?right :left; 

    }

儘管這適用於大多數情況下，如果樹是這樣的，問題是最近公共祖先（1，2，3），或2和3最低共同祖先，其中根== 1;

1 -> 2 -> 3

然後在我看來，答案該解決方案將提供爲2，這是因爲遞歸後

left = null 
right = 2

而實際的答案是1

但是這個解決方案工作。有人能幫助我理解我在這裏發生了什麼錯誤。

來源

2016-05-08 Clockwork

這種情況下'p'和'q'是什麼？ –

不，我認爲在後面的部分，你提供了樹結構，但沒有提供方法的其他兩個輸入參數，所以很難討論發生了什麼。 –

按照邏輯：

lowestCommonAncestor(root=1, p=2, q=3): 
    if (root == null || root == p || root == q) return root; 
    //  false   false  false 

    left = lowestCommonAncestor(2, 2, 3): 
       if (root == null || root == p || root == q) return root 
       //  false   true    return 2 

    right = lowestCommonAncestor(null, 2, 3): 
       if (root == null || root == p || root == q) return root; 
       //  true        return null 

    return left != null && right != null ? root : left == null ? right : left; 
    //   true  false      false    : 2

結果：跟隨代碼2

最簡單方法是使用調試。

來源

2016-05-08 13:02:43 Andreas

的TreeNode right = lowestCommonAncestor(root.right, p, q);執行後，

你：

left=null; 
right=2;

，最後的結果= (left!=null && right!=null)?root:(left==null?right:left);

返回結果：2

來源

2016-05-08 13:10:24 triffic

在Java中以遞歸方式遞歸的最低公共祖先

回答

相關問題