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

[funnycoderstar]

JavaScript实现LeetCode第236题： 二叉树的最近公共祖先

题目描述

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

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

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

               3
             /  \
            5    1
           / \   / \
          6   2 0   8
             /  \     
            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 为不同节点且均存在于给定的二叉树中

解题方法

使用递归：

fx 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：
(f(lson) && f(rson)) || ((x === p || x === q) && (f(lson) || f(rson)))

1. 左子树和右子树均包含 p节点或q节点，如果左子树包含的是 p 节点，那么右子树只能包含 q节点。反之亦然，因为 p 节点和 q 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 x 就是我们要找的最近公共祖先
2. x 恰好是 p 节点或 q 节点且 它的左子树或右子树有一个包含了另一个节点的情况，因此满足满足这个条件也可以说明 xx 就是我们要找的最近公共祖先。

我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 fx 本身的定义很巧妙，在找到最近公共祖先 x 以后，fx 按定义被设置为 true ，即假定了这个子树中只有一个 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}
 */
var lowestCommonAncestor = function(root, p, q) {
    let result = null;
    function 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)) {
            result = root;
        }
        return lson || rson || (root.val === p.val || root.val === q.val);
    }
    dfs(root, p, q);
    return result;
};

• 时间复杂度： O(N)。其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
• 空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。