https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

难度：中等

---

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

  百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉树中。

解法1：保存祖先节点+逐个判断

  一个很直的方法就是对树进行深度优先遍历，并在遍历过程中使用一个栈保存遇到的节点，直到遍历到节点 p 或节点 q 为止（包括这个节点）。

  此时，栈中保存了 p 或 q 的所有祖先节点，将栈中节点一个个出栈，对每个节点判断其子树中是否 包含另一个节点（若栈中保存的是 p 的祖先节点，则判断是否包含 q ，反之亦然），当遇到第一个包含另一个节点的祖先节点，这个节点就是最近的公共祖先节点。

JS 代码：

var lowestCommonAncestor = function(root, p, q) {
    let stack = [];
    let flag = false;
    let tmp;
	
    // 对树进行深度优先遍历，保存路径上的节点
    const dfs = (root) => {
        if (flag || !root) {
           return;
        }

        stack.push(root);
        if (root === p || root === q) {
            flag = true; // 当找到其中一条路径后，可提前退出
            tmp = root;
            return;
        }

        dfs(root.left);
        dfs(root.right);
        if (!flag) {
            stack.pop();
        }
    }; 

    dfs(root);
    flag = false;
    // 对每个节点判断子树中是否包含另一个节点
    const check = (root) => {
        if (flag || !root) {
            return;
        }

        if ((root === p || root === q) && root !== tmp) {
            flag = true;
            return;
        }

        check(root.left);
        check(root.right);
    };

    for (let i = stack.length-1; i >= 0; i--) {
        check(stack[i]);
        if (flag) {
            return stack[i];
        }
    }
};

  上面的代码中，对树的深度优先遍历可替换为后序非递归遍历，这样的话就不用考虑非祖先路径上的节点问题了。

解法2：深度优先遍历

  解法2来源于 LeetCode ，主要思路是在遍历过程中根据左右子树是否包含了 p 节点或 q 节点来寻找祖先节点。

  即根据逻辑表达式：(lson && rson) || ((root.val === p.val || root.val === q.val) && (lson || rson)) 来进行判断当前节点 root 是否为祖先节点。

  该表达式包括了两种情况，lson 表示左子树中是否包含 p 或 q 节点，rson 表示右子树中是否包含 p 或 q 节点：

• lson && rson 表示左右子树中包含了 p 节点和 q 节点，这两个节点是在不同的子树中
• (root.val === p.val || root.val === q.val) && (lson || rson) 表示当前节点为 p 或 q 节点的情况，且此时当前节点的子树中包含了另一个节点（因为两个节点值是不同的，所以只要 lson 或 rson 中有一个为真就代表了包含了另一个节点）。

JS 代码如下，其中 flag 用于提前退出递归：

var lowestCommonAncestor = function(root, p, q) {
    let ans, flag = false;
    const dfs = (root) => {
        if (!root || flag) {
            return false;
        }

        let lson = dfs(root.left);
        let rson = dfs(root.right);
        if ((lson && rson) || ((root.val === p.val || root.val === q.val) && (lson || rson))) {
            ans = root;
            flag = true;
            return true;
        }
        return lson || rson || root.val === p.val || root.val === q.val;
    }

    dfs(root);

    return ans;
};

解法3：记录祖先节点

  解法 3 来源于 LeetCode

  解法 3 中的记录祖先节点和解法 1 中的不同，解法 1 是使用数组顺序记录了 p 、q 其中一个节点中的祖先节点路径，而解法 3 中则是以节点值为索引来将祖先节点保存在数组中，这样，我们就能根据 p 和 q 节点的值往上跳来找到公共的祖先节点。

  具体做法是遍历这两个节点的祖先节点，并使用一个数组 vis 来标识某个节点是否被访问过，若我们先遍历 p 的祖先节点，则在遍历 q 的祖先节点时，遇到的第一个被访问过的祖先节点就是它们的最近公共祖先节点。

JS 代码：

var lowestCommonAncestor = function(root, p, q) {
    let ans;
    let fa = [];
    let vis = [];
    fa[root.val] = false;

    const dfs = (root) => {
        if (!root) {
            return;
        }

        if (root.left) {
            fa[root.left.val] = root;
            dfs(root.left);
        }
        if (root.right) {
            fa[root.right.val] = root;
            dfs(root.right);
        }
    };

    dfs(root);
    while (p) {
        vis[p.val] = true;
        p = fa[p.val];
    }

    while (q) {
        if (vis[q.val]) {
            return q;
        }
        q = fa[q.val];
    }
};