236. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

来源：LeetCode

思路

深度优先搜索，遍历所有节点，遍历的过程中发现目标节点（p 或 q），记录下当前的栈，栈中全是该节点的祖先。第二次遍历到目标节点时，可以结束遍历，获取到当前的栈，是该节点的祖先。然后一个个弹出，验证是否是之前栈中元素。第一个找到的即是结果

解法

/**
 * 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}
 */
const lowestCommonAncestor = (root, p, q) => {
  const visited = new Set([null]);
  const targetNodes = new Set([p, q]);
  let ancestors;
  const stack = [];

  stack.push(root);

  while (stack.length) {
    const peek = stack[stack.length - 1];
    visited.add(peek);

    if (targetNodes.has(peek)) {
      if (!ancestors) {
        ancestors = new Set(stack);
        targetNodes.delete(peek);
      } else {
        break;
      }
    }

    const { left, right } = peek;

    if (!visited.has(left)) {
      stack.push(left);
      continue;
    }

    if (!visited.has(right)) {
      stack.push(right);
      continue;
    }

    stack.pop();
  }

  while (stack.length) {
    const node = stack.pop();
    if (ancestors.has(node)) {
      return node;
    }
  }
};