本文转载自微信公众号《三分钟学会前端》，作者安姐。转载本文请联系三分钟学习前端公众号。有关树的基础知识，请参见此处：初学者树给定一棵二叉树，找到树中两个指定节点的最近公共祖先。百度百科对最近共同祖先的定义是：“对于有根树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是不同的节点，都存在于给定的二叉树中。答案：递归实现解题思路：如果树是一棵空树或者p和q中的任意一个节点是根节点，那么p和q最近的公共节点就是根节点。如果不是，则二叉树不是空树，p和q为非根节点，递归遍历左右子树，得到左右子树的最近公共祖先。如果p和q节点存在于左右子树的最近共同祖先中，则说明p和q节点分布在左右子树的根节点处，此时二叉树的最近共同祖先为根。如果左子树中p和q节点的最近共同祖先为空，则p和q节点位于左子树上，最终二叉树的最近共同祖先是右子树上的p,q。q节点的最近共同祖先如果右子树中p和q节点的最近共同祖先为空，则决策逻辑与左子树中p和q节点的最近共同祖先相同。如果p和q节点在左右子树的最近共同祖先中如果所有祖先都为空，则返回null代码实现：constlowestCommonAncestor=function(root,p,q){if(root==null||root==p||root==q)returnrootconstleft=lowestCommonAncestor(root.left,p,q)constright=lowestCommonAncestor(root.right,p,q)if(left===null)returnrightif(right===null)returnleftreturnroot};复杂度分析：时间复杂度：O(n)空间复杂度：O(n)
