二叉树问题的LCA
提问于 2012-08-22 22:24:46
我编写了一个代码，用于查找二叉树中节点的最小共同祖先，但它似乎返回了null而不是LCA。
我的算法如下。
- 递归地在树的左右枝中找到祖先
- 其中左树和右树的节点在LCA中具有匹配的元素。 公共类LCA { public静态BinaryTreeNode findLCA( BinaryTreeNode root，BinaryTreeNode node1，BinaryTreeNode node2) { if (root == null) {返回空；} BinaryTreeNode左= root.getLeft()；BinaryTreeNode右= root.getRight()；if (左!= null &(左= null &(左== node1 =左== node2)) (返回根)；} if (右!= null&(右== node2)en19#)){返回根；} if (findLCA(左，node1，node2) != null) &(findLCA(右，node1，node2) != null){返回根；}返回null；}
这段代码有什么问题？
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-08-22 22:35:19
我想我能修好它。我添加了另一个条件来查看递归findLCA是否返回了什么。如果是这样的话，我将进一步返回相同的值，从而解决了问题。请提供您的意见，如果这个设计是可以的。
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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12085869
复制
腾讯云开发者
