java - 二叉树问题的LCA

Question

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

我的算法如下。

1. 在树的左右分支中递归查找祖先

2. 左树和右树在 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; }}
   

这段代码可能有什么问题？

Answer 1

我想我能够修复它。我添加了另一个条件来查看我的递归 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;        
}