二叉树的最近公共祖先

https://leetcode-cn.com/explore/interview/card/bytedance/244/linked-list-and-tree/1026/

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

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

image.png

这个题一般的思路，先找到p和q的路径，然后去他们的最大前缀的点
但是有个更好的递归的思路，不过非常难理解。
首先 如果 p和q是在root的两边找到的，那么他们的最近的公共祖先应该是root
如果root的left找到的p和q，那说明root的right肯定为None了，那么他们的公共祖先应该是root.left。反之是root.right。
有了这个逻辑，再加上写好递归的返回条件即可。
递归的代码如下：

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root ==q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        if left:
            return left
        if right:
            return right