1.树好难啊。
这是一道在二叉搜索树中找根节点的值的题目。给两个值val1和val2,找它们的根节点。
链接:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
这题比较简单,因为二叉搜索树的特性,就是左边的树小于根节点,右边的树大于根节点。
所以只要找到 val1<root and val2>root
的情况就行了。
2.题解:
循环:
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
while root:
# 都小于root节点,向左边找
if p.val < root.val and q.val < root.val:
root = root.left
# 都大于root节点,向右边找
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root.val
递归
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
# 都小于root节点,向左边找
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
# 都大于root节点,向右边找
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root.val
网友评论