Sword finger Offer 68 - II. The recent public ancestor of the binary tree

topic：

Sword finger Offer 68 - II. The recent public ancestor of the binary tree.md

Thought：

Termination condition：

Dangyan leaves，Return directly null ；
when root equal p,qp, qp,q ，Return directly root ；

Recursive work：

Open the recursive Zuozi node，Return to value left ；
Open recursive right -child node，Return to value right ；

return value： according to left and right ，Can be expanded in four situations；

1. when left and right At the same time as an empty ：illustrate root Left / Nothing in the right tree is not included p,q，return null ；
2. when left and right Not empty at the same time ：illustrate p,q Be included in root of Heterochrome （Respectively Left / Right -handed tree），therefore root For the recent public ancestors，return root ；
3. when left Is empty ，right 不Is empty ：p,q Nothing root Left子树middle，直接return right 。Specific can be divided into two cases：
   1. p,q One of them is root of Right -handed tree middle，at this time right direction p（Assume p ）；
   2. p,q Both nodes are there root of Right -handed tree middle，at this timeof right direction Public ancestor node recently ；
4. when left 不Is empty ， right Is empty ：Situation 3. Same；

Code：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # If you find a number，But I didn't find another number，就直接illustrate他们不在同一个子树middle
        if not root or root == p or root == q:
            return root
        # 递归Left子树
        left = self.lowestCommonAncestor(root.left, p, q)
        # 递归Right -handed tree
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果Left子树andRight -handed tree都不Is empty，illustratepandqRespectivelyLeftRight -handed treemiddle，那么when前节点就是他们of公共祖先
        if left and right:
            return root
        # 如果Left子树Is empty，illustratepandq都在Right -handed treemiddle，那么Right -handed treeof公共祖先就是他们of公共祖先
        if not left:
            return right
        # 如果Right -handed treeIs empty，illustratepandq都在Left子树middle，那么Left子树of公共祖先就是他们of公共祖先
        if not right:
            return left