問(wèn)題描述
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, null, null, 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.
補(bǔ)充說(shuō)明：
給定了一個(gè)二叉搜索樹刻坊，輸入兩個(gè)值，然后求這兩個(gè)值得最近公共祖先仓洼。
方案分析
- 筆者做這個(gè)題的時(shí)候忘記了一個(gè)問(wèn)題，導(dǎo)致感覺(jué)這個(gè)題寫起來(lái)比較復(fù)雜悉稠。后來(lái)參照了別人的解法才恍然大悟届囚。這里都說(shuō)了是一個(gè)二叉搜索樹枫虏，那么盾鳞，這里隱藏的一個(gè)條件是搜索樹是有序的！
- 父節(jié)點(diǎn)的值肯定是大于左孩子節(jié)點(diǎn)的值诡挂，小于右邊孩子節(jié)點(diǎn)的值碎浇。那么給定兩個(gè)要搜索的值，它的最近共同祖先的要不就是介于兩個(gè)值之間璃俗，要不就是等于較小值奴璃。（等于是當(dāng)兩個(gè)搜索值在同側(cè)的情況下，其中的一個(gè)搜索值作為自己本身的祖先）城豁。
- 先上基本解法的遞歸寫法苟穆。
python實(shí)現(xiàn)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root:
return
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
方案分析2
- 遞歸并不是一個(gè)好的方法，換非遞歸的唱星。
python實(shí)現(xiàn)2
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root, p, q):
while root:
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
方案分析3
- 在別人那看到一個(gè)應(yīng)用數(shù)學(xué)特性解決問(wèn)題的方式雳旅，效率提升明顯。
- 如果一個(gè)值x的大小介于a,b之間间聊，那么(x-a)*(x-b)<=0攒盈。這不正是二叉搜索樹的特性么。
python實(shí)現(xiàn)3
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root, p, q):
while (root.val-p.val)*(root.val-q.val) > 0:
if root.val > max(p.val, q.val):
root = root.left
else:
root = root.right
return root
