235. Lowest Common Ancestor of a Binary Search Tree

题目：

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              
    ___2__          ___8__
   /              /      
   0      _4       7       9
         /  
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

链接：　　http://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

一刷，思想是判断当前节点的值

1.与输入的两值之一相等，查找另一值是否在树里，是则当前值是LCA，否则返回None

2.当前值在两值中间，查找输入两值是否在树里，都在则返回当前值，否则返回None

3.当前值比最小值小或比最大值大，更新当前值

问题，若输入查找的值是None，输出None还是另外一值呢？

 1 class Solution(object):
 2     @staticmethod
 3     def find(root, p):
 4         if not p:
 5             return False
 6         cur = root
 7         while root:
 8             if root.val == p.val:
 9                 return True
10             if root.val < p.val:
11                 root = root.right
12             else:
13                 root = root.left
14         return False
15         
16     def lowestCommonAncestor(self, root, p, q):
17         """
18         :type root: TreeNode
19         :type p: TreeNode
20         :type q: TreeNode
21         :rtype: TreeNode
22         """
23         if not root:
24             return root
25         if not p or not q:
26             return None
27         small = p if p.val < q.val else q
28         large = p if p.val >= q.val else q
29 
30         cur = root
31         while cur:
32             if cur.val == small.val:
33                 return cur if Solution.find(cur, large) else None
34             if cur.val == large.val:
35                 return cur if Solution.find(cur, small) else None
36             if small.val < cur.val < large.val:
37                 if Solution.find(cur, small) and Solution.find(cur, large):
38                     return cur
39                 else:
40                     return None
41             cur = cur.right if cur.val < small.val else cur.left
42         return None

如果没有找到node可以返回另一个的话，二刷可以试一下recursive解法。