二叉树的最近公共祖先

Question

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

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

思路

分情况讨论：

p、q是兄弟：最近公共祖先是父节点
p、q是平级但不是同一个父节点：最近公共祖先是父节点的父节点的……
p、q是祖先关系：最近公共祖先是p或q

遇到这个题目首先想的是要是能自底向上查找就好了，如果两个节点自底向上最终交汇到一个节点，那个节点就是最近公共祖先。

如果想要从下往上，用后序遍历，递归的返回值应该是p或q节点，如果返回值不为空说明找到了目标节点

var lowestCommonAncestor = function(root, p, q) {
    //终止条件
    if(root===null) return null
    if(root===p||root===q)  return root
    //单层逻辑
    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)
    if(left===null&&right===null){      //左右子树都没找到
        return null 
    }else if(left===null&&right!=null){ //右子树找到了
        return right
    }else if(left!=null&&right===null){ //左子树找到了
        return left
    }else{
        return root                     //左右子树都找到了
    }
};

二叉树的最近公共祖先 ​

思路 ​

二叉树的最近公共祖先

思路