이진 트리 문제의 LCA

Question

이진 트리에서 노드의 공통 조상을 찾는 코드를 작성했지만 LCA 대신 null을 반환하는 것으로 보입니다.

내 알고리즘은 다음과 같습니다.

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가 뭔가를 반환하는지 확인하기 위해 다른 조건을 추가했습니다. 그렇다면 동일한 가치를 더 반환하여 문제를 해결했습니다. 이 디자인이 괜찮 으면 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;   
}