LeetCode 241. 二叉树的最近公共祖先

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

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

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

解法一 递归

通常关于树的问题都是用递归来解决，最重要的就是分解、找到重复的子问题。

首先我们来看看什么是最近公共祖先

什么是公共祖先呢？就是子树里面包含了 p q 节点，同时，最近的要求就以为着，左子树和右子树里面都需要有该节点。

转换为代码，条件就是 (leftSon && rightSon) || (x = p || x = q) && (leftSon || rightSon)

时间复杂度 O(n) 空间复杂度 O(n)

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

解法二 存储父节点

• 向上访问，直到出现交集点

• 模式识别，判断是否出现过或者出现次数的问题，可以使用散列表

时间复杂度为 O(n)，空间复杂度为 O(n)