题目描述：
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.
题目大意：
给定一棵二叉搜索树（BST），寻找BST中两个给定节点的最近公共祖先（LCA）。
根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”
例如，题目描述的样例中，节点2和8的最近公共祖先（LCA）是6。另一个例子，节点2和4的LCA是2，因为根据LCA的定义，一个节点可以是其本身的后继。
解题思路：
根据BST的性质，左子树节点的值＜根节点的值，右子树节点的值＞根节点的值
记当前节点为node，从根节点root出发 若p与q分别位于node的两侧，或其中之一的值与node相同，则node为LCA 否则，若p的值＜node的值，则LCA位于node的左子树 否则，LCA位于node的右子树
Python代码：
迭代版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
while (p.val - root.val) * (q.val - root.val) > 0:
root = [root.left, root.right][p.val > root.val]
return root
递归版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
if (p.val - root.val) * (q.val - root.val) <= 0:
return root
elif p.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return self.lowestCommonAncestor(root.right, p, q)
本文链接：http://bookshadow.com/weblog/2015/07/11/leetcode-lowest-common-ancestor-binary-search-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
