Niedrigste gemeinsame Vorfahren rekursiv in Java

Question

Ich habe eine Lösung für die niedrigste gemeinsame Vorfahren Problem in Java in Leetcode gefunden. Das Problem, das anders angegeben ist, ist, den niedrigsten gemeinsamen Vorfahren von p und q mit dem BST zu finden, der an Wurzel verwurzelt ist. Hier ist mein Code.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
     if(root == null || root == p || root == q) return root; 
     TreeNode left = lowestCommonAncestor(root.left, p, q); 
     TreeNode right = lowestCommonAncestor(root.right, p, q); 
     return left != null && right != null ? root : left == null?right :left; 

    } 

Während dies für die meisten Fälle funktioniert, wenn der Baum in etwa so ist und die Frage ist Lowest Common Ancestor (1, 2, 3) oder den niedrigsten gemeinsamen Vorfahr von 2 und 3, wo root == 1;

1 -> 2 -> 3 

Dann ist diese Lösung die Antwort meiner Meinung nach ist 2 liefert, Dies, weil nach der Rekursion ist

left = null 
right = 2 

während die eigentliche Antwort 1.

ist jedoch diese Lösung funktioniert. Kann mir jemand helfen zu verstehen, was ich hier falsch mache?

Answer 1

folgen der Logik:

lowestCommonAncestor(root=1, p=2, q=3): 
    if (root == null || root == p || root == q) return root; 
    //  false   false  false 

    left = lowestCommonAncestor(2, 2, 3): 
       if (root == null || root == p || root == q) return root 
       //  false   true    return 2 

    right = lowestCommonAncestor(null, 2, 3): 
       if (root == null || root == p || root == q) return root; 
       //  true        return null 

    return left != null && right != null ? root : left == null ? right : left; 
    //   true  false      false    : 2 

Ergebnis: 2

Der einfachste Weg, um den Code zu folgen ist einen Debugger zu verwenden.

Answer 2

Nach Ausführung von TreeNode right = lowestCommonAncestor(root.right, p, q);,

Sie erhalten:

left=null; 
right=2; 

Endlich das Ergebnis = (left!=null && right!=null)?root:(left==null?right:left);

Return Ergebnis: 2