题解 | #在二叉树中找到两个节点的最近公共祖先#

/*

• function TreeNode(x) {
• this.val = x;
• this.left = null;
• this.right = null;
• } */

/** *

• @param root TreeNode类
• @param o1 int整型
• @param o2 int整型
• @return int整型 */

思路:每个root进递归函数，

先看1.是否有值2.是不是要找的两个节点；

都不是，那就继续找这个root的左、右子树:

左右节点只有其中一个能找到o1或o2，就返回这个左/右节点；

左右节点都能找到，说明这个root就是最近的祖先节点；

都没找到返回null；

function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    //节点为null，则返回nul
    if(!root){
        return null
    }
    //该节点就是o1或o2的位置，就返回root
    if(root.val == o1||root.val == o2) return root.val
    //不是o1 o2的位置，就继续找root的左右子树
    let left = lowestCommonAncestor(root.left,o1,o2);
    let right = lowestCommonAncestor(root.right,o1,o2);
    //
    if(left&&!right){
        return left
    }
    if(right&&!left){
        return right
    }
    if(!right&&!left){
        return null
    }
    return root.val


}
module.exports = {
    lowestCommonAncestor : lowestCommonAncestor
};