leetcode 235. Lowest Common Ancestor of a Binary Search Tree
LeetCode of Tree search Binary Common
2023-09-14 09:11:52 时间
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,0,4,7,9,null,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 nodes2
and8
is6
.
Example 2:
Input: root, p = 2, q = 4 Output: 2 Explanation: The LCA of nodes2
and4
is2
, 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
相关文章
- [LeetCode] Length of Last Word - 最后一个单词的长度
- Java实现 LeetCode 816 模糊坐标(暴力)
- Java实现 LeetCode 777 在LR字符串中交换相邻字符(分析题)
- Java实现 LeetCode 501 二叉搜索树中的众数
- Java实现 LeetCode 440 字典序的第K小数字
- Java实现 LeetCode 434 字符串中的单词数
- Java实现 LeetCode 392 判断子序列
- Java实现 LeetCode 273 整数转换英文表示
- Java实现 LeetCode 187 重复的DNA序列
- Java实现 LeetCode 37 解数独
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- (LeetCode 160)Intersection of Two Linked Lists
- LeetCode:111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy
- [Javascript] Use an Array of Promises with a For Await Of Loop
- [LeetCode] Intersection of Two Arrays
- [LeetCode] Power of Three | Power of Two
- Leetcode 最大子序和
- Leetcode 680. 验证回文字符串 Ⅱ(待解决)
- 【Leetcode】Length of Last Word
- leetcode 19 -- Remove Nth Node From End of List
- leetcode 345. Reverse Vowels of a String
- leetcode 191. Number of 1 Bits
- leetcode 599. Minimum Index Sum of Two Lists
- leetcode 637. Average of Levels in Binary Tree
- 【Leetcode刷题Python】404. 左叶子之和