이진 트리의 LCA

이진 트리가 주어지면 트리에서 주어진 두 노드의 최저 공통 조상(LCA)을 찾으십시오.

Wikipedia의 LCA 정의에 따르면 다음과 같습니다. ”



예 1:
입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
출력: 3
설명: 노드 5와 1의 LCA는 3입니다.

예 2:
입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
출력: 5
설명: 노드 5와 4의 LCA는 5입니다. 노드는 LCA 정의에 따라 자신의 자손이 될 수 있기 때문입니다.

예 3:
입력: 루트 = [1,2], p = 1, q = 2
출력: 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root) return null;

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

  const lac1 = lowestCommonAncestor(root.left, p, q);
  const lca2 = lowestCommonAncestor(root.right, p, q);

  if (lac1 !== null && lca2 !== null) {
    return root;
  }

  if (lac1 !== null) {
    return lac1;
  }

  return lca2;
};