首先要明白二叉搜索树的特性,左子树所有的节点小于根节点,右子树所有的节点大于根节点,因此可以分别对两个值进行二叉树搜索,找出对应的路径,再找出最后的一个相同节点,即是最近的共同节点
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param root TreeNode类 # @param p int整型 # @param q int整型 # @return int整型 # class Solution: def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int: # write code here if not root: return 0 lLeft = self.findPath(root, p) lRight = self.findPath(root, q) res = 0 for i in range(len(lLeft)): if lLeft[i] in lRight: res = lLeft[i] return res def findPath(self, root: TreeNode, k:int): ls = [] while root: ls.append(root.val) if root.val == k: break if k > root.val: root = root.right else: root = root.left return ls