235. 二叉搜索树的最近公共祖先

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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 
        if root.val > p.val and root.val > q.val:
            left = self.lowestCommonAncestor(root.left,p,q)
            return left 
        elif root.val < p.val and root.val < q.val:
            right = self.lowestCommonAncestor(root.right,p,q)
            return right 
        else:                     # 在 两点之间。 
            return root 

        # 迭代
        # while root!=None:
        #     if root.val > p.val and root.val > q.val:
        #         root = root.left 
        #     elif root.val < p.val and root.val < q.val:
        #         root = root.right 
        #     else:
        #         return root