二叉树问题的LCA [英] LCA of Binary Tree Issue

问题描述

我已经编写了一个代码，用于在二叉树中查找节点的最小公共祖先，但是它似乎返回 null 而不是LCA。

I have written a code for finding least common ancestor of nodes in binary tree but it seems to return null instead of the LCA.

我的算法如下。

1. 递归地找到左边的祖先树的右分支



2. 左和右树在LCA中具有匹配元素的节点。

1. Recursively find the ancestor in left and right branch of tree

2. A node where left as well as right tree has matching elements in the LCA.

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; }}

这可能是什么问题代码？

What could be the problem with this code?

推荐答案

我认为我能够解决它。我添加了另一个条件，以查看我的递归findLCA是否返回了某些东西。如果是这样，我会进一步返回相同的值，从而解决了该问题。

I think I am able to fix it. I added another condition to see if my recursive findLCA is returning something. If so I return the same value further which fixed the issue. Plz provide your comments if this design is ok.

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;        
}

这篇关于二叉树问题的LCA的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！