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