原题
给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例1：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例2：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
解法
思想
利用二叉搜索树的性质，两个节点p、q可以有两种分布情况：
1. 分别位于公共祖先的左、右子树。
2. 其中一个节点就是公共祖先，另一个节点位于子树上。
如此递归查找。
代码
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;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode235-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e7%9a%84%e6%9c%80%e8%bf%91%e5%85%ac%e5%85%b1%e7%a5%96%e5%85%88/
相关推荐
-
leetcode53-最大子序和
原题 原题 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入： [-2,1,-3,4,-1,2,1,-5,4],...
-
leetcode3-无重复字符的最长子串
原题 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例1： 输入： "abcabcbb" 输出： 3 解释： 因为无重复字符的最长子串是 "abc"，所以其长...
-
leetcode221-最大正方形
原题 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 ...
-
leetcode119-杨辉三角II
原题 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶： ...
-
leetcode994-腐烂的橘子
原题 在给定的网格中，每个单元格可以有以下三个值之一： 值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜...
-
leetcode344-反转字符串
原题 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间...
-
leetcode572-另一个树的子树
原题 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树...
-
leetcode146-LRU缓存机制
原题 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) -...
-
leetcode18-四数之和
原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 ta...
-
二叉树中序遍历-折纸问题
原题（来源牛客网） 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯...