235.Lowest Common Ancestor of a Binary Search Tree
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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given binary search tree: root = [6,2,8,4,7,9,null,3,5] _______6______ / ___2__ ___8__ / / 0 _4 7 9 / 3 5 Example 1: Input: root = [6,5],p = 2,q = 8 Example 2: Input: root = [6,q = 4 Note:
# Definition for a binary tree node. class TreeNode: def __init__(self,x): self.val = x self.left = None self.right = None class Solution: def lowestCommonAncestor(self,root,p,q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root: return None if root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left,q) #这里需要return,因为不需要回溯,找到就可以了 elif root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right,q) else: return root (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |