LeetCode|50/235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”例如,给定如下二叉搜索树:root = [6,2,8,0,4,7,9,null,null,3,5]_______6______
/\
___2_____8__
/\/\
0_479
/\
35
示例 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 为不同节点且均存在于给定的二叉搜索树中。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if((root.val >= p.val && root.val <= q.val) || (root.val >= q.val && root.val <= p.val))
return root;
if(root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right,p,q);
if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left,p,q);
return null;
}
}
【LeetCode|50/235. 二叉搜索树的最近公共祖先】二叉搜索树,肯定是root节点和左右两边数值大小的判断!
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 数据结构和算法|LeetCode 的正确使用方式