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.
Use property of BST.
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution(object): 9 def lowestCommonAncestor(self, root, p, q): 10 """ 11 :type root: TreeNode 12 :type p: TreeNode 13 :type q: TreeNode 14 :rtype: TreeNode 15 """ 16 if root is None: 17 return root 18 if p.val > q.val: 19 return self.lowestCommonAncestor(root, q, p) 20 if p.val < root.val and q.val > root.val: 21 return root 22 elif p.val < root.val and q.val < root.val: 23 return self.lowestCommonAncestor(root.left, p, q) 24 elif p.val > root.val and q.val > root.val: 25 return self.lowestCommonAncestor(root.right, p, q) 26 return root
Lowest Common Ancestor of a Binary Search Tree 解答
原文：http://www.cnblogs.com/ireneyanglan/p/4934904.html