Lowest Common Ancestor of a Binary Tree

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/932/

典型的DFS，方法需要熟记。

（1） 同时在左子树和者右子树需要common ancestor，如果p，q同时存在于左子树，则return左子树返回值，反之亦然

（2）如果p和q分别分布在左右子树，则当前node就是共同ancestor。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(node,p,q):
            if node == None:
                return
            if node.val == p.val or node.val == q.val:
                return node
            l = dfs(node.left,p,q)
            r = dfs(node.right,p,q)
            if l and r:
                return node
            if l:
                return l
            return r
        return dfs(root,p,q)