每日一练：LeeCode-235、二叉搜索树的最近公共祖先【二叉搜索树+DFS+从上往下】

本文是力扣每日一练：LeeCode-235、二叉搜索树的最近公共祖先【二叉搜索树+DFS+从上往下】学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。

思路

在做这道之前可以先去我的博客每日一练：LeeCode-236、二叉树的最近公共祖先【二叉树+DFS+从下往上】回顾一下判断二叉树的最近公共祖先的判断

1、本题要求 返回该树中两个指定节点的最近公共祖先，很明显就是树递归中，返回一条边的思路
2、两种树的搜索情况，根据题目而定

在⼆叉树：公共祖先问题中，如果递归函数有返回值，如何区分要搜索⼀条边，还是搜索整个树。
搜索⼀条边的写法：

if (递归函数(root.left)) return ;
if (递归函数(root.right)) return ;

搜索整个树写法：

left = 递归函数(root.left);
right = 递归函数(root.right);
left与right的逻辑处理;

本题就是标准的搜索⼀条边的写法，遇到递归函数的返回值，如果不为空，⽴刻返回。

3、如何找到公共祖先？是关键！
因为二叉搜索树是有序树，所有 如果中间节点是 q 和 p 的公共祖先，那么 中节点的数组⼀定是在 [p, q]区间的。即 中节点 >p && 中节点 < q 或者中节点 > q && 中节点 < p。
所以这里从上往下遍历，遇到 cur节点是数值在[p, q]区间中则⼀定可以说明该节点cur就是q 和 p的公共祖先。
是否一定是最近公共祖先呢？可以从以下 代码随想录 图解1、2中，发现，确实当 cur节点是数值在[p, q]区间时，该节点cur才是q 和 p的公共祖先。
为何一定是从上往下遍历，不是从下往上呢？是因为本题是二叉搜索树，即有序树，若是二叉树，只能参考二叉树的最近公共祖先的回溯过程

图解1：
在这里插入图片描述
图解2：

递归法

1、确定递归函数返回值以及参数
参数就是当前节点，以及两个结点 p、q。
返回值是要返回最近公共祖先，所以是TreeNode

TreeNode traversal(TreeNode cur, TreeNode p, TreeNode q)

2、确定终⽌条件
遇到空返回就可以了，但是本题是这个最近公共祖先一定存在，所以，不要也可以

// if (cur==null)return cur;

3、确定单层递归的逻辑
1）寻找区间[p.val, q.val]（注意这⾥是左闭右闭）

2）在寻找区间过程中，需要判断是向左遍历？还是向右遍历？
①若 cur.val ⼤于 p.val和 q.val，那么就应该向左遍历（说明⽬标区间在左⼦树上）。
①若 cur.val 小于 p.val和 q.val，那么就应该向右遍历（说明⽬标区间在右⼦树上）。

3) 需要注意的是此时不知道p和q谁⼤，所以两个都要判断

        if (cur.val > p.val && cur.val > q.val){TreeNode left = traversal(cur.left,p,q);if (left!=null)return left;}if (cur.val < p.val && cur.val < q.val){TreeNode right = traversal(cur.right,p,q);if (right!=null)return right;}

4)剩下的情况，就是cur节点在区间（p.val <= cur.val && cur.val <= q.val）或者（q.val <= cur.val &&cur.val <= p.val）中，那么cur就是最近公共祖先了，直接返回cur。

	return cur;

整体代码

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return traversal(root,p,q);}TreeNode traversal(TreeNode cur, TreeNode p, TreeNode q){// if (cur==null)return cur;// 无中逻辑if (cur.val > p.val && cur.val > q.val){	// 左TreeNode left = traversal(cur.left,p,q);if (left!=null)return left;}if (cur.val < p.val && cur.val < q.val){	// 右TreeNode right = traversal(cur.right,p,q);if (right!=null)return right;}return cur;}
}