[Binary Tree - DFS, Medium] Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

탈출조건은 current가 null이거나, p거나, q일 때

left와 right 탐색 시 모두 존재하면 - current node가 LCA이므로 current node 리턴

left나 right 탐색 시 하나만 존재하면 - 조상 못찾은것이기 때문에 있는 쪽만 리턴

최종적으로 한 쪽 서브트리에서 값을 찾았으나 다른 쪽에서는 못찾게 되는 경우 그 값이 LCA가 될 수 있음을 증명한다.
왜? 다른 서브트리에는 해당 값이 없다는게 확실, 찾은 한 쪽 (p or q)으로 시작하는 서브트리에 나머지 하나가 있다는 뜻이 되므로

요약

• left != null && right != null 인 경우: 확실히 current node가 LCA임
• 그 외
  • left != null인 경우: 확실히 right가 left쪽 서브트리에 포함됨.
  • right != null인 경우: 확실히 left가 right쪽 서브트리에 포함됨.
  • 즉, 해당 서브트리의 루트(left 또는 right)를 리턴함으로써 해당 재귀 시점의 값으로 쓰이거나 아니면 자기 자신이 LCA가 됨

class Solution {
    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);

        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}