74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
1. 解题思路
这道题首先的想法就是二分,先搜索第一列,找到一个合适的行,然后再在行里面二分
2. AC代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
//先在列里面二分,找到一个合适的位置,使得matrix[i][0]<=target<=matrix[i+1][0]
int l = 0,r = matrix.length-1;
//定义搜索区间[l,r],当l<=r的时候,区间依然存在,可以搜索
int row = -1;
if(matrix[0][0] > target){
return false;
}
while(l<=r){
int mid = (l+((r-l)>>1));//右移1bit=/2
if(mid == matrix.length-1){
row = mid;
break;
}
if(matrix[mid][0] == target){
return true;
}
if(matrix[mid][0] < target && matrix[mid+1][0]> target){
//那么这个mid就是我们要找的
row = mid;
break;
}else if(matrix[mid][0] > target){
r = mid-1;
}else if(matrix[mid][0] < target){
l = mid+1;
}
}
if(row == -1){
return false;
}
l = 0;r = matrix[0].length-1;
while (l<=r){
int mid = (l+((r-l)>>1));
if(target == matrix[row][mid]){
return true;
}else if(matrix[row][mid] > target){
r = mid-1;
}else if(matrix[row][mid] < target){
l = mid+1;
}
}
return false;
}
}剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 10001. 解题思路
首先这道题的特征是:每一行是有序的,每一列也是有序的,第一个想法就是检查每一列,检查锁定一行,但是其实这样的想法是无法找到答案的,因为题目并没有说到下一行的所有元素都大于上一行的元素,因此必须转变思路
首先我们以暴力的思路来思考这道题,首先就是我们可以遍历每一行,在每一行上进行二分,这样的话我们肯定能够找到答案,但是,这是高效的吗?我们发现,我们在二分的时候实际上是检查了多余的元素的,比如说以下样例
我们想找13对吧,那么在搜索的时候,我们会在第一行搜索到11这个元素,但是我们明显发现11这个元素是不符合要求的,换言之,小于等于11的那些元素全部不符合要求,然而我们在检查第二行的时候,我们发现我们依然会去检查小于等于11的那些元素,比如说2 5 8,这样的话就造成了检查资源的浪费
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],该怎么优化呢?
我们打算减少检查那些不必要检查的元素,我们必须找出这个矩阵元素排布的规律
首先,正向思考,我们以
martix[2][2]为例,我们思考上下左右的元素的特点为了避免区间漏解,我们假设搜索区间是一块区域,这个区域以
[x,y]为起点,以左下角为终点,那么包含所有可能答案的[x,y]就是[0,m-1][ [1, 4, 5, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
我们知道,查找与搜索的核心就是不断压缩解空间,在我们如上的定义中,解空间就是x,y的值,我们需要根据当前x和y的值,来不断变换我们的解空间,直到解出答案为止
2. AC代码
public boolean searchMatrix(int[][] matrix, int target) {
//定义右上角
int x = 0;
int y = matrix[0].length;
//右上角都是不断向下面、左边收缩,因此我们让它不越下面的界,左边的界就可以了
while (x<matrix.length && y >= 0){
if(target == matrix[x][y]){
return true;
}else if(target < matrix[x][y]){
x++;
}else if(target > matrix[x][y]){
y--;
}
}
return false;
}剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
1. 解题思路
- 第一种思路:直接找到变小的地方,直接返回就行
这道题,关键是旋转之前是升序的,在旋转之后就会产生一个下降的点,这个下降的点就是数组中的最小元素
如果数组中存在的元素全都是一样的,那么就要返回这个数字
- 第二种思路:二分搜索
我们知道,这种旋转操作,我们先讨论旋转次数<n的情况,在这种情况下,一定会产生两半数组,这两半数组一半是左数组,一半是右数组,左数组中的值一定是大于右数组中的值的,我们需要利用这个特性,将右数组压缩到只剩下一个元素,那么在这个时候,剩下的这个元素就一定就是那个旋转点了,下面具体来说一下怎么压缩
首先我们使用两个指针,让这两个指针指向l=0,r=nums.length-1
注意哈,这里是假设产生了左右数组的,没有产生左右数组的情况我们后续再来讨论
中点取mid = l+(r-l)>>1
- 假设
nums[mid]>nums[l],我们知道左数组的值一定是大于右数组中的值的,因此mid不可能存在右数组中,因此这时候mid肯定存在于左数组,那么这个mid有啥用呢?它可以用来帮助我们减少搜索量,缩小搜索区间,因此这时候我们可以将左指针变为l=mid+1 - 假设
nums[mid]<nums[l],我们知道右数组的值一定是小于左数组中的值的,因此mid不可能存在左数组中,因此这时候,或许你会问,如果相等的话那不就在左数组中了吗?是的,这是第三点我们需要考虑的复杂情况,因此我们先不讨论,先搞定这个,同样的,这个mid可以帮助我们减少搜索量,但是值得注意的是,这时候右指针变化的情况是r=mid,而不是r=mid-1,为什么呢?这是因为我们想要我们的搜索区间[l,r]始终包含这个旋转点,如果你r=mid-1了,让这个r跨越过了右数组到了左数组,那么就找不到了呀 - 然后又会问了,那么为什么
l=mid+1又可以的咧?这是因为,就算我们l=mid+1跨越了左数组,由于之前判断mid肯定是位于左数组的,当mid+1变成了右数组,那么这时候会导致旋转点丢失吗?答案是不会的,这是因为我们始终保持了右指针在右数组中,因此无论如何,[l,r]都会至少包含一个元素,这样的话就肯定不会丢失旋转点,而恰巧的,这就启发我们如何决定结束条件了 - 假设
nums[mid]==nums[l],注意,这时候mid无法判断是在左数组还是在右数组,这时候依然要缩小解空间,关键还是如何缩小解空间,并且不会丢失旋转点?我们假设两种情况的发生,然后执行相关的操作,观察:- 假设我们执行
l=mid+1的操作,如果mid位于左数组就还好,不会引发任何问题,但是mid位于右数组,那就寄了,就直接把这个搜索区间搞烂了,没办法搜索 - 同样的,我们执行
r=mid的时候,假设mid位于左数组,也会把搜索区间搞烂掉,那怎么办?
- 假设我们执行
- 这时候一个核心思路就是让我们的指标指针
跳出这个相等的区域,那么安全的办法就是让l++- 这时候会有个问题,假设
l++不断执行,假如l跳到了右数组,这时候会发生什么? - 此时必然会产生
nums[l]<nums[mid],这时候我们第一时间就返回这个nums[l]就可以了 nums[l]==nums[mid]呢?这个的话可以算作为极端情况,可以推算此时是全部的元素都一样,因为你无论怎么旋转,都和旋转n次的情况一样的,因此我们放到后面来讨论哈。
- 这时候会有个问题,假设
- 好了,接下来讨论有关旋转n次的情况,当旋转了n次,这时候
nums[l]<nums[r],这时候我们可以直接断言nums[l]就是最小值,直接return即可。
2. AC代码
public int minArray(int[] numbers) {
if(numbers.length == 1){
return numbers[0];
}
for(int i = 0;i < numbers.length-1;i++){
if(numbers[i] > numbers[i+1]){
return numbers[i+1];
}
}
return numbers[0];
}public class MinArray2 {
public int minArray(int[] numbers) {
if(numbers[0]<numbers[numbers.length-1]){
return numbers[0];
}
int l = 0, r = numbers.length-1;
while (l<r){
if(numbers[l] < numbers[r]){
return numbers[l];
}
int mid = l + ((r-l)>>1);
if(numbers[l] == numbers[mid]){
l++;
}else if(numbers[l] > numbers[mid]){//mid在右数组
r = mid;
}else if(numbers[l] < numbers[mid]){
l = mid+1;
}
}
return numbers[l];
}
}剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
1. 解题思路
这道题是一个简单的层次遍历,采用队列的数据结构即可
2. AC代码
class Solution {
public int[] levelOrder(TreeNode root) {
//简单的层次遍历
if(root == null){
return new int[0];
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
List<Integer> list = new ArrayList<>();
while(!q.isEmpty()){
TreeNode head = q.poll();
list.add(head.val);
if(head.left != null){
q.offer(head.left);
}
if(head.right != null){
q.offer(head.right);
}
}
int[] ans = new int[list.size()];
int idx = 0;
for (Integer integer : list) {
ans[idx++] = integer;
}
return ans;
}
}剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
1. 解题思路
这道题与上一道的不同点在于,我们需要区分出哪个节点是那一层的,那么要怎么做呢?
这道题的关键是一次遍历只遍历一层的数据,因此可以用while+for的策略,具体见代码
2.AC代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int idx = 0;
List<List<Integer>> list = new ArrayList<>();
while (!q.isEmpty()){
int size = q.size();
list.add(new ArrayList<>());
for(int i = 0;i<size;i++){
TreeNode head = q.poll();
list.get(idx).add(head.val);
if(head.left != null){
q.offer(head.left);
}
if(head.right != null){
q.offer(head.right);
}
}
idx++;
}
return list;
}
}剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
1. 解题思路
这道题的关键是之字形,可以用一个变量来进行计数,偶数的话就调用addFirst(),奇数的话就调用addLast()
2.AC代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int idx = 0;
List<List<Integer>> list = new ArrayList<>();
while (!q.isEmpty()){
int size = q.size();
//System.out.println(size);
list.add(new LinkedList<>());
for(int i = 0;i<size;i++){
TreeNode head = q.poll();
//手动实现addLast和addFirst
if(idx % 2 != 0){
list.get(idx).add(0,head.val);
}else{
list.get(idx).add(i,head.val);
}
if(head.left != null){
q.offer(head.left);
}
if(head.right != null){
q.offer(head.right);
}
}
idx++;
}
return list;
}
}剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
1. 解题思路
如果树B是树A的子结构,那么子结构的根节点可能是树A的任意一个节点,因此判断树B是否是树A的子结构,需要完成如下工作
- 先序遍历树A中的每个节点
nA, - 判断树A中以
nA为根节点的子树是否包含树B
算法流程
首先将A的根节点称作为A,将B的根节点称作为B
定义检查函数recur(A,B)
- 当A为空的时候,此时越过了A的叶子节点,必定匹配失败
- 当B为空的时候,此时全部匹配,匹配成功
- 当A和B的节点的值不同,这时候也匹配失败
定义遍历函数isSubStructure(A,B)
- 以节点A的根节点为父,检查B是否是A的子结构
- 以节点A.left为父,检查B是否是A.left的子结构
- 以节点A.right为父,检查B是否是A.right的子结构
2. AC代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean rercur(TreeNode A,TreeNode B){
if(B == null){
return true;
}
if(A == null){
return false;
}
if(A.val != B.val){
return false;
}
return rercur(A.left,B.left)&&rercur(A.right,B.right);
}
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B==null){
return false;
}
//前序遍历
return rercur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
}剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
1. 解题思路
二叉树的解题纲领
- 是否可以通过遍历一遍二叉树来得到答案?如果可以,就用一个
traverse()函数配合外部的变量来进行实现,这叫做遍历的思维模式- 是否可以通过定义一个递归函数,通过子问题(子树)推导出原问题的答案?如果可以,那么就写出这个递归函数的定义,并充分利用返回值,这叫做
分解问题的思维模式如果单独抽取出一个二叉树节点,它需要做什么事情?需要在什么位置
前/中/后序位置来做?其他的节点交给递归函数进行处理
对于这道题来说,我们要做的事情是这样的:
4
/ \
2 7
/ \ / \
1 3 6 9将这棵树变成:
4
/ \
7 2
/ \ / \
9 6 3 1不难发现,这道题,我们从根节点开始,交换根节点的左右节点,然后交换左右节点的左右节点,依次下去,最终就能够得到一棵翻转后的二叉树,我们利用以上的思维方式进行这道题的思考
可以通过遍历思维模式来解这道题吗
既然是遍历,那么就要通过前序/中序/后序的某一个特定的遍历顺序对树进行遍历,而且在一个最简单的情况下执行操作,遍历这棵树上的每一个节点,让每一个节点下的左右节点交换他们的位置就可以了
那么是前序/后序/中序呢?这个的话可以依靠模拟,我们假设是前序遍历,那么也就是在递归到深层的节点之前,就执行节点的交换
4
/ \
2 7
/ \ / \
1 3 6 9->
4
/ \
7 2
/ \ / \
6 9 1 3->
4
/ \
7 2
/ \ / \
9 6 1 3我们发现前序遍历是可以解决问题的,同理,后序也能,但是中序是不行的。
可以通过分解问题的思维模式来解这道题吗
分解问题的思维的关键是,将处理具体落实到树上的每一个子节点,要反转整棵树,那么就要翻转以根节点的左/右节点的这棵子树,所以可以设计出一个递归函数,invertTree(root):代表翻转根节点为root的子树
2.AC代码
遍历法
class Solution {
//遍历解法
private void traverse(TreeNode root){
if(root == null){
return ;
}
//后遍历
traverse(root.left);
traverse(root.right);
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
public TreeNode mirrorTree(TreeNode root) {
traverse(root);
return root;
}
}子问题分解法
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode t = root.left;
root.left = root.right;
root.right = t;
return root;
}
}剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1. 解题思路
同样的,我们以遍历法和分解子问题的角度来思考这个问题
子问题分解
我们知道,如果以root为根节点的树,如果root的左子树和root的右子树是对称的,那么这棵树就是对称的
所以的话,依据这个思路可以使用分解子问题的思路,定义递归函数
bool sub(TreeNode left,TreeNode right)
当以left节点为根的树和以right为根的树是对称的,那么就返回true
base-case
当left和right为空的时候,证明此时匹配成功
当left和right只有一个为空,匹配失败
当left和right都不为空,判断left.val和right.val是否相等,相等则返回true,继续向下递归
2. AC代码
class Solution {
private boolean rercur(TreeNode left,TreeNode right){
if(left == null && right == null){
return true;
}
if(left == null || right == null){
return false;
}
if(left.val == right.val){
return rercur(left.left,right.right)
&& rercur(left.right,right.left);
}else{
return false;
}
}
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return rercur(root.left,root.right);
}
}剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
1. 解题思路
2.AC代码
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
1.解题思路
首先一种最直观的思路就是:如果我们能够从节点p和q向上遍历搜索,找到p和q汇聚的那一个公共节点,那么就可以找出答案,但是我们知道二叉树是的指针是从父节点指向子节点的,而子节点是没有指针指向父节点的,因此直接遍历的一条路是行不通的
但是,我们能不能利用递归遍历的这个过程,逐层返回的特性,来达到这个效果呢?
我们知道当递归达到最深层的时候,这时候就会按照递归函数的定义向上返回一些数据,那么这个返回的值就很关键了,我们拿一组样例过来说话
4
/ \
2 7
/ \ / \
1 3 6 9假设我们要找1和6的公共祖先对吧,首先我们要考虑的问题是怎么遍历这棵树?
我们知道,公共祖先节点的特征是p和q分别位于左右子树,那么也就意味着,我必须要先检查完我的左右子树,检查完之后,下层会给我返回一个值,我再根据这个值来做判断,那么先检查左右子树是什么特征呢?就是后序遍历
按照左右根的遍历方式,遍历到最左边的1,这时候向上返回一个TreeNode,代表找到了,然后返回到2,到了2之后,这时候根据结果:左子树返回不为空,右子树返回为空,这时候还没有找到公共祖先节点,于是仅返回左子树的结果,告诉root节点左子树有p或者q
同理的,root的右子树最终也会返回一个p和q的特征值到root
最终,就能够得出答案为root了
特殊情况
假设我们的p是1,q是2这时候应该返回2,也就是说p和q本身就是公共祖先的这种情况,这种情况需要在代码中特殊处理。
2. AC代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){//如果遍历到空节点,那么就证明你在这个子树中没有找到p或者q
return root;
}
if(root.equals(p) || root.equals(q)){//当在子树中查询到节点,那么将结果向上返回
return root;
}
//然后交给单层遍历逻辑
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null){
return root;
}
if(right != null){
return right;
}
if(left != null){
return left;
}
return null;
}
}关于特殊处理
假设p本身就是公共祖先,那么这时候就会直接返回了,对于最终的答案没有任何影响
235 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
1. 解题思路
首先看到这个二叉搜索树,假设我们要找的节点是0和3,入口是root,于是我们根据二叉搜索树的特性,我们发现0和3都比root的6要小,那么就他们俩肯定位于左子树,于是我们去查左子树
然后我们发现2是大于0的,2是小于3的,因此可以断定,0肯定位于2的左子树,3肯定位于2的右子树,那么这时候2肯定就是最近公共祖先
为什么肯定是最近公共祖先
公共祖先这一点是显然的,因为右子树不存在符合条件的节点,只可能在左子树,而2是左子树的根节点,必然成立,但是为什么是最近的呢?
我们假设一下,假如最近的还位于下面的某个节点,那么我肯定就要向左遍历或者向右遍历对吧
但是这时候要记住,p是位于左子树的,q是位于右子树的,如果向左遍历,那么我将错过q,如果向右遍历,我将错过p,根据这个特点,我们知道肯定就是最近的了
2. AC代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return root;
}
int small = Math.min(p.val,q.val);
int large = Math.max(p.val,q.val);
return traverse(root,small,large);
}
private TreeNode traverse(TreeNode root,int small,int large){
if(root == null){
return null;
}
if(root.val < small && root.val < large){
TreeNode right = traverse(root.right,small,large);
if(right != null){
return right;
}
}
if(root.val > small && root.val > large){
TreeNode left = traverse(root.left,small,large);
if(left != null){
return left;
}
}
return root;
}
}注意一点,我一开始写出了这样的代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return root;
}
int small = Math.min(p.val,q.val);
int large = Math.max(p.val,q.val);
return traverse(root,small,large);
}
private TreeNode traverse(TreeNode root,int small,int large){
if(root == null){
return null;
}
if(root.val > small && root.val < large){
return root;
}
if(root.val > small && root.val > large){
return traverse(root.left,small,large);
}
return traverse(root.right,small,large);
}
}交上去发现样例都无法通过,这是因为考虑漏了情况,就是我们在上面说的,当p和q本身就是祖先节点的时候,这时候就产生问题,它本身就是祖先节点了,那你还去搜索子树干嘛?因此这时候直接返回本节点就行,那么如果要修改,要咋改捏?打个补丁就行:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return root;
}
int small = Math.min(p.val,q.val);
int large = Math.max(p.val,q.val);
return traverse(root,small,large);
}
private TreeNode traverse(TreeNode root,int small,int large){
if(root == null){
return null;
}
if(root.val > small && root.val < large){
return root;
}
if(root.val == small || root.val == large){
return root;
}
if(root.val > small && root.val > large){
return traverse(root.left,small,large);
}
return traverse(root.right,small,large);
}
}
