二叉树的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问题

回答

相关问题