236 二叉树的最近公共祖先

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

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

题解

要是我们能从下往上找就好了，比如说任意节点p,q。 如果我们能从下往上找，那么直接往上走碰到的第一个节点就是公共祖先。 但是二叉树是不可能从下往上找的，但是回溯（对于后序遍历）可以。所以我们可以通过后序遍历来实现。

递归三部曲

1.确定递归函数的参数和返回值， 参数是root, p, q。 返回值是最近公共祖先。

2.确定终止条件，如果是null返回，如果碰到p，也返回，表明找到了就不需要继续往下找了。同理q也是 所以终止条件为 if(!root || root.val === p.val || root.val === q.val) return root

3.单层逻辑,如果左子树有值，右子树也有值，说明此时就是结果（p, q分别列在左右子树结果中） 如果左子树有值，右子树没值，返回左子树，表明左子树已经找到，但是右子树没有找到。 如果左子树没值，右子树有值，返回右子树，表明右子树已经找到，但是左子树没有找到。 如果都没有值，返回null，表明在这个子树上并没有找到p, q祖先。

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

    if(left && right) {
        //当前节点是结果
        return root
    }
    if(left && !right) {
        //采用left当做结果
        return left
    }
    if(!left && right) {
        //采用right当做结果
        return right
    }
    return null

整体解法

var lowestCommonAncestor = function(root, p, q) {
    if(!root || root.val === p.val || root.val === q.val) {
        return root
    }
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

    if(left && right) {
        //当前节点是结果
        return root
    }
    if(left && !right) {
        //采用left当做结果
        return left
    }
    if(!left && right) {
        //采用right当做结果
        return right
    }
    return null
};