236. 二叉树的最近公共祖先

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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':
        # 基线条件
        if root==None: return None
        # 后续 从下往上找 公共点。
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if (left and right) or root==p or root==q:
            return root 
        elif left==None and right==None:
            return None
        elif left and right==None:
            return left 
        elif left==None and right:
            return right