leetcode 235. Lowest Common Ancestor of a Binary Search Tree
发布时间:2020-12-14 04:49:18 所属栏目:大数据 来源:网络整理
导读: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 v and w as the lowest node in
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 v and w as the lowest node in T that has both v and w 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,p = 2,q = 8 Output: 6 Explanation: The LCA of nodes and is . 286 Example 2: Input: root,q = 4 Output: 2 Explanation: The LCA of nodes and is,since a node can be a descendant of itself according to the LCA definition. # 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 """ node = root while node: if node.val in {p.val,q.val}: return node elif node.val > p.val and node.val > q.val: node = node.left elif node.val < p.val and node.val < q.val: node = node.right else: return node (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |