0236. 二叉树的最近公共祖先.md

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

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

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

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

递归。

/**
 * 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) {
    let ans = root;
    const dfs = (r) => {
        if (!r) return null
        const left = dfs(r.left, p, q)
        const right = dfs(r.right, p, q)
        if ((left && right) || (
            (r.val === p.val || r.val === q.val) && (left || right)
        )) {
            ans = r
        }
        return left || right || (r.val === p.val || r.val === q.val)
    }
    dfs(root)
    return ans
};

哈希表，好像会超时？

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
const parents = new Map()

var dfs = (root) => {
    if (root.left) {
        parents.set(root.left.val, root)
        dfs(root.left)
    }
    if (root.right) {
        parents.set(root.right.val, root)
        dfs(root.right)
    }
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    dfs(root)
    const visited = new Set()

    while (p) {
        visited.add(p.val)
        p = parents.get(p.val)
    }
    while (q) {
        if (visited.has(q.val)) {
            return q
        }
        q = parents.get(q.val)
    }
    
    return null
};