[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

---

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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);
        return left == null ? right : right == null ? left : root;
    }
}

Explanation

• 공통된 조상을 찾으려면 노드 p와 q의 위치를 찾아야하고, 그러기 위해선 아래쪽으로 내려가면서 노드를 탐색하는 반복이 필요하다. 해당 풀이는 재귀 호출을 통해 반복을 수행하도록 한다.
• 먼저 전체 트리를 탐색하기 위해서 메서드 내에서 재귀 호출이 2번 필요하므로 root노드의 왼쪽과 오른쪽 자식노드를 이용해 재귀 메서드를 2번 호출한다.

  lowestCommonAncestor(root.left, p, q);
  lowestCommonAncestor(root.right, p, q);
  

• 재귀 호출 과정에서 재귀 호출이 종료될 수 있도록 조건이 필요하다. 노드 p와 q를 찾고 있으므로 종료 조건은 해당 노드가 p 또는 q일 때가 되어야 한다.

  if (root == p || root == q) return root;
  

• 종료 조건을 통해 노드 p또는 q를 찾았다면 해당 노드를 활용해 공통된 조상 노드를 찾아야 하므로 TreeNode left와 right를 선언하여 재귀 호출을 통해 찾은 노드 p 또는 q를 할당해준다.

  TreeNode left = lowestCommonAncestor(root.left, p, q); // left = p 또는 q
  TreeNode right = lowestCommonAncestor(root.right, p, q); // right = p 또는 q
  

• 호출된 메서드 내에서 노드 left와 right를 찾았다면 호출된 메서드의 파라미터였던 root 노드를 반환하면 해당 노드가 공통된 조상이 된다.

  return root;
  

• 하지만 노드 left또는 right에 노드 p 또는 q가 할당되지 않을 수가 있다. 이 경우는 노드 p와 q가 문제로 주어지는 트리 좌측 또는 우측에 몰려있다는 의미가 된다. 따라서 재귀 함수를 호출 할 때 root.left 또는 root.right를 찾지 못하는 에러가 발생하게 되고, 이를 방지하기 위하여 종료 조건을 추가한다. 그리고 이 때는 노드 left 또는 right 중 비어있지 않은 노드가 생기게 되는데 이를 반환하면 해당 노드가 공통된 조상이 된다.

  if (root == null || root == p || root == q) return root;
  return left == null ? right : right == null ? left : root;