leetcode236-二叉树的公共祖先

leetcode 236

思路

由于我们遍历一个二叉树都是从上往下遍历的，这里要找公共祖先，我们希望的是从下往上遍历，这要怎么实现呢？
如果了解二叉树的遍历就知道，如果使用后序遍历：左右中，就是先拿到左右节点再一层层往上返回的，那么我们本题解答也需要利用到后序遍历来实现
另外我们使用递归法进行后序遍历，那么终止条件是什么呢？
由于我们需要找到公共组件，所以如果我们找到了p节点或q节点时，我们就应该进行记录，所以这种情况要把root返回，还有一种情况就是遍历到了叶子节点的左右节点，root为空，此时也要终止遍历
左右递归遍历的话相信大家都不陌生了，但是因为我们要拿到上次遍历的结果来做判断，所以需要有个值来接受，我们定义left和right来接受到值，当出现p或者q的时候，那么我们的left或者right就是不为空的，如果左右都不为空，那说明当前节点为公共祖先
如果left为空，right不为空呢？
left为空，right不为空，这时候right的父节点需要接受到right的值，所以需要把right向上返回
left不为空，right为空也是同理，这样一层层向上返回得到的就是最大公共祖先

情况二

像示例2这样，可能存在p是q的公共祖先，其实按照前面的解答也是有涵盖的，当遍历到p的时候发现root === p，那么我们就直接return root，此时p后序的节点都不会遍历，然后再一层层的把p往上抛出，最终拿到的值就是p节点

实现

var lowestCommonAncestor = function(root, p, q) {
    const deep = (root)=>{
        if(root === p || root === q || !root) return root;
        // 左
        const left = deep(root.left)
        // 右
        const right = deep(root.right)
        // 中
        if(left && right) return root;
        if(left && !right) return left;
        if(!left && right) return right;
    }
    return deep(root);
};