题解 | #在二叉树中找到两个节点的最近公共祖先#

注意o1和o2是int，最后返回的也是int
postOrder的作用：

1. 如果o1和o2都在，返回root；
2. 如果有一个在，返回那一个；
3. 都不在，返回None

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        def postOrder(root, o1, o2):              
            if not root or root.val==o1 or root.val==o2:                
                return root            
            left_LCA = postOrder(root.left, o1, o2)
            right_LCA = postOrder(root.right, o1, o2)            
            if left_LCA and right_LCA:
                return root
            elif (not left_LCA) and (not right_LCA):
                return None
            else:
                if left_LCA:
                    return left_LCA
                else:
                    return right_LCA
        return postOrder(root, o1, o2).val