leetcode with python:235. Lowest Common Ancestor of a Binary

题目:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

给定一个binary search tree和其中两个Node,找出两个Node的最近共同祖先

这题我一开始没注意到是binary search tree,结果就当普通的binary tree去做了
没利用到binary search tree的性质当然会慢上许多
不过可以用在一般binary tree上我就分享一下吧

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        if not root:            return 0        l=self.lowestCommonAncestor(root.left,p,q)        r=self.lowestCommonAncestor(root.right,p,q)                if l not in [0,1]:            return l        if r not in [0,1]:            return r        cnt=0        if root==p or root==q:            cnt=1         if cnt+l+r==2:            return root        else:            return cnt+l+r

我是用计数器+递迴的方式去实作
一旦遇到目标节点,计数器就加1
而计数器计到2时,就不再回传计数器的值,而是回传让计数器变为2的节点(最近共同祖先)
最后执行时间104ms(faster than 66.72%)

用了binary search tree的性质,这题会轻鬆许多

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        while True:            if root.val<q.val and root.val<p.val:                root=root.right            elif root.val>q.val and root.val>p.val:                root=root.left            else:                return root

binary search tree性质:
左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值

藉此性质,我们的搜索会轻鬆许多
由上往下搜索
若root的值小于两个目标节点(表示此节点非最近共同祖先),就向右搜索
若root的值大于两个目标节点(表示此节点非最近共同祖先),就向左搜索
而当root的值介于两个目标节点之间,则代表我们找到了最近共同祖先
直接回传即可
最后执行时间82ms(faster than 92.73%)

那我们下题见