问题描述
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).”
_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5
For example, the lowest common ancestor (LCA) of nodes 2
and 8
is 6
. Another example is LCA of nodes 2
and 4
is 2
, since a node can be a descendant of itself according to the LCA definition.
原问题链接:https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
问题分析
这个问题相对很简单,只要知道二叉搜索树的都知道,它的一个基本特性就是 任何一个节点,它比自己的左子树值大,同时比自己的右子树小。所以如果要给定树上面两个节点,并查找它最低公共父节点的话,可以这样来考虑:
首先考虑最低公共父节点,既然是最低的公共父节点,必然这个节点是如下几种情况,
1. 存在一个节点,给给定的两个节点分别在它的左右子树中。这种情况最常见,如下图:
在该图中,我们选择的节点是6和9,它们最低公共父节点是8.
2. 一个节点是另外一个节点的父节点,这种情况我们也可以称那个处于父节点位置的节点为它们的最低公共父节点,如下图:
在该图中,5节点是6节点的父节点,它也就是它们的最低公共父节点。
既然我们要找的是两个节点的最低公共父节点,所以它们都有一个比较有意思的特征,就是该最低公共父节点一定满足 m.val >= p.val && m.val <= q.val,假设p, q表示我们给定的两个节点。为什么不是m节点的父节点呢?因为m节点必然是它父节点的左子节点或者右子节点。这样它的父节点相对节点p, q就不满足上述的关系了。
既然定义好了这个特性我们就来进一步分析怎么来查找这个节点。我们首先能够访问的节点是根节点root。对于该节点来说,如果p, q两个节点的值都小于它的值,则说明这两个节点在它的左子树,我们可以到它的左子树做进一步的查找。如果p, q两个节点的值都大于它的值,则说明应该去它的右子树查找。而对于其他的情况则说明我们找到了符合条件的节点。这样我们可以得到如下的代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q); if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q); return root; } }
非常简单,没什么好说的。当然,我们也可以写一个非递归版的实现:
public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(true) { if(root.val > p.val && root.val > q.val) root = root.left; else if(root.val < p.val && root.val < q.val) root = root.right; else return root; } } }
总结
这个问题总的来说还是比较好找思路。重点在于它的最低父节点满足m.val > p.val && m.val < q.val。而且它们互为充分必要条件。所以我们要找这个节点的时候只需要根据当前节点和两个节点的值比较去选择下一步去哪个子树就可以了。当然,从这个问题衍生出来的问题还有更复杂的,比如针对普通二叉树的情况,它不是二叉搜索树,那么这种情况该怎么处理呢?我们在后面的文章中继续讨论。
相关推荐
1123.Lowest_Common_Ancestor_of_Deepest_Leaves最深叶节点的最近公共祖先【LeetCo
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode的题目:Balanced Binary Tree
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
LeetCode::laptop:LeetCode解决方案
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
of Two Sorted Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove ...
最终450 Love Babbar 450问题
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
LeetCode 101:和你一起你轻松刷题(C++)
Leetcode:Leetcode提交
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode:leetcode刷题
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode 762: Prime Number of Set Bits in Binary Representation Leetcode 766: Toeplitz Matrix Medium Leetcode 392: Is Subsequence Leetcode 767: Reorganize String Leetcode 769: Max Chunks To Make ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
Leetcode:LeetCode解题代码