二叉樹的LCA問題

我已經編寫了一個代碼，用於查找二叉樹中最小公共節點的祖先節點，但它似乎返回null而不是LCA。二叉樹的LCA問題

我的算法如下。

遞歸發現在樹

其中左以及右樹已匹配在LCA元件A節點的左和右分支中的祖先。

public class LCA { 
    public static BinaryTreeNode findLCA(BinaryTreeNode root, BinaryTreeNode node1 , BinaryTreeNode node2) {  

if (root == null) { 
    return null; 
}  

BinaryTreeNode left = root.getLeft(); 
BinaryTreeNode right = root.getRight(); 

if (left != null && (left == node1 || left == node2)) { 
    return root;     
} 

if (right != null && (right == node1 || right == node2)) { 
    return root;     
} 

if ((findLCA(left, node1, node2) != null) && (findLCA(right, node1, node2) != null)) {   
    return root; 
} 

return null; }}

什麼能與此代碼的問題？

來源

2012-08-23 Manish

'但這不行 - 「你遇到什麼不受歡迎的行爲？ – amit

@amit，這不是返回給我的lca，而是返回null – Manish

算法效率非常低。改爲嘗試以下方法：從節點1和節點2將樹中向上的路徑收集到根節點。然後比較從結尾開始的兩個列表以查找兩個列表中存在的最後一個項目。這是最接近的共同祖先，複雜度只是O（深度（樹）），在平衡二叉樹中是O（log n），而在最壞的情況下，你的方法可能在O（n）中運行。當然，如果您沒有將反向鏈接組成一個父節點，我的方法將無法工作。 – Sebastian

我想我可以解決它。我添加了另一個條件來查看我的遞歸findLCA是否正在返回一些東西。如果是這樣，我會進一步返回相同的值，從而解決問題。如果這個設計沒問題，Plz會提供您的意見。

public static BinaryTreeNode findLCA(BinaryTreeNode root, BinaryTreeNode node1 , BinaryTreeNode node2) {  

    if (root == null) { 
     return null; 
    }  

    BinaryTreeNode left = root.getLeft(); 
    BinaryTreeNode right = root.getRight(); 
    BinaryTreeNode lcaNode1; 
    BinaryTreeNode lcaNode2; 

    if (left != null && (left == node1 || left == node2)) { 
     return root;     
    } 

    if (right != null && (right == node1 || right == node2)) { 
     return root;     
    } 
    lcaNode1 = findLCA(left, node1, node2); 
    lcaNode2 = findLCA(right, node1, node2); 

    if ((lcaNode1 != null) && lcaNode2 != null) {   
     return root; 
    } 

    if (lcaNode1 != null) { 
     return lcaNode1; 
    } 

    if (lcaNode2 != null) { 
     return lcaNode2; 
    }  

    return null;   
}

來源

2012-08-23 06:35:19 Manish

而不是將其添加爲答案，您應該更新原始問題。 –

@chander，好的。有關算法的任何建議？ – Manish

二叉樹的LCA問題

回答

相關問題