leetcode_235

发表于   |   分类于

Lowest Common Ancestor of a Binary Search Tree

题目戳这

题意

给你一颗二叉搜索树，然后问其中任意两个点的最近公共祖先(LCA)

解法

这道题目因为是有序的二叉树，所以我们可以利用’有序’这个性质来求解任意两个点(p, q)的LCA，刚开始有初始的节点，我们叫做root,分以下三种情况

  1. 当p,q的值一个小于root，一个大于root的值，那么说明此时root就是p,q两个节点的LCA
  2. 当p节点的值小于root时(q就不用管了，我们先判断了第一个条件，如果第一个条件不成立，说明此时q的值也是小于root的)，那么p, q的LCA应该就是在root的左分支上。
  3. 当p节点的值大于root时，那么p, q的LCA应该就是在root的右分支上。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if (root.val - p.val) * (root.val - q.val) <= 0:
            return root
        
        if p.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)