难度：中等

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

    百度百科中最近公共祖先的定义为：“对于有根树 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
    2. 输出: 3
    3. 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

    image.pngimage.png

    解题思路：
    根节点为空，根节点中只包含P或只包含q,直接返回根节点
    利用递归遍历左子树和右子树，如果左子树为空则直接返回右子树（此时right已为左右子树的最近公共祖先）;如果右子树为空则直接返回左子树（此时left已为左右子树的最近公共祖先）
    如果左右子树都不为空，说明节点分布在两侧，直接返回根节点
    时间复杂度为O(N)，空间复杂度为O（N）

    1. var lowestCommonAncestor = function(root, p, q) {
    2.     if(!root || root===p || root===q) return root;
    3.     let left=lowestCommonAncestor(root.left,p,q);
    4.     let right=lowestCommonAncestor(root.right,p,q);
    5.     if(!left) return right;
    6.     if(!right) return left;
    7.     return root;
    9. };