目录
- 前言
- 二叉搜索树中的众数
- 二叉树的最近公共祖先
- 二叉搜索树的最近公共祖先
- 总结
前言
又是学习LeetCode二叉树的新一天，今天还是接着学习一下二叉搜索树的内容，希望博主记录的内容能够对大家有所帮助 ，一起加油吧朋友们！💪💪💪
二叉搜索树中的众数
LeetCode题目链接
给一个含重复值的二叉搜索树的根节点root，返回该树的所有众数（以数组格式）
思路梳理：这道题其实也是可以利用二叉搜素数中序遍历节点值递增的规律来写，因为就是可以在递归遍历的时候去更新当前节点频率和最大节点频率来完成这样，当当前节点频率大于等于最大节点频率时就把当前节点的值加入到一个整数列表中🤔🤔🤔
我们接下来梳理递归三要素
- 确定递归的参数和返回值
// 定义了结果的列表所以无需返回值，然后前序节点值和当前频率、最大频率用变量保存故参数只有数的根节点即可
private void inOrderTraversal(TreeNode root){}
- 确定递归的出口
//因为要处理每个节点所以会进入空节点
if(root == null) return;
- 确定递归的单层逻辑
//递归单层处理逻辑
inOrderTraversal(root.left);// 递归遍历左子树
if(root.val == preVal){ // 处理当前节点
curCount++;
}else{
curCount = 1;
}
if(curCount > maxCount){ // 判断是否需要更新众数列表
maxCount = curCount;
result.clear();
result.add(root.val);
}
else if(curCount == maxCount){// 如果当前频率等于最大频率也加入到众数列表中
result.add(root.val);
}
preVal = root.val;// 更新前一个节点的值为当前值
inOrderTraversal(root.right);// 递归遍历右子树
完整代码如下
/**递归法 */
class Solution {
private int maxCount = 0; //最大频率
private int curCount = 0;//当前频率
private int preVal = Integer.MIN_VALUE;//记录前一个节点的值
private List<Integer> result = new ArrayList<>();//记录众数结果
public int[] findMode(TreeNode root) {
inOrderTraversal(root);
return result.stream().mapToInt(Integer::intValue).toArray();
}
private void inOrderTraversal(TreeNode root){ //中序遍历
//递归出口
if(root == null) return;
//递归单层处理逻辑
inOrderTraversal(root.left);
if(root.val == preVal){ //更新频率
curCount++;
}else{
curCount = 1;
}
if(curCount > maxCount){ //更新众数
maxCount = curCount;
result.clear();
result.add(root.val);
}
else if(curCount == maxCount){
result.add(root.val);
}
preVal = root.val;//更新存储的前节点的值
inOrderTraversal(root.right);
}
}
这里可以提一下的是最后将列表转换成整型数组的一步操作
return result.stream().mapToInt(Integer::intValue).toArray();
.stream()是java 8引入的Stream API中的一个方法，用于从集合（ 如List、Set、Map等）或数组生成一个流（Stream）🤔
List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
names.stream() // 生成流
.filter(name -> name.startsWith("A")) // 过滤出以"A"开头的名字
.forEach(System.out::println); // 输出满足条件的名字
mapToInt()是 Java Stream API 提供的用于将流中的对象映射为基本类型的方法，类似的方法还有mapToDouble()和mapToLong()等。
List<Integer> numbers = Arrays.asList(1, 2, 3, 4);
int[] result = numbers.stream()
.mapToInt(Integer::intValue) // 将 Integer 转换为 int
.toArray(); // 转换为 int[]
// result 是 [1, 2, 3, 4]
intValue()是Integer类的一个方法，它的作用是将Integer对象转换为基本数据类型int。在 Java 中，包装类（如Integer、Double等）都有类似的转换方法，将包装类的对象转换为对应的基本数据类型。
result.stream().mapToInt(Integer::intValue).toArray();
result.stream().mapToDouble(Double::doubleValue).toArray();
result.stream().mapToLong(Long::longValue).toArray();
我们也来梳理一下迭代法
- 主要就是中序遍历需要先把root节点压栈，然后把左子树节点递归入栈，然后弹出root节点进行处理，处理完后递归处理右节点，处理的逻辑和递归一样，然后的话就是栈一开始为空，循环条件加上一个当前节点不为空，而当前节点初始化为root🤔🤔🤔
/**迭代法 */
class Solution {
public int[] findMode(TreeNode root) {
int maxCount = 0; //最大频率
int curCount = 0;//当前频率
int preVal = Integer.MIN_VALUE;//记录前一个节点的值
List<Integer> result = new ArrayList<>();//记录众数结果
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){ //中序遍历得先把中和左给压栈
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop(); //弹出中节点
if(cur.val == preVal){
curCount++;
}else{
curCount = 1;
}
if(curCount > maxCount){
maxCount = curCount;
result.clear();
result.add(cur.val);
}else if(curCount == maxCount){
result.add(cur.val);
}
preVal = cur.val;
cur = cur.right;//处理右节点
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
二叉树的最近公共祖先
LeetCode题目链接
给定一个二叉树，找到该树中两个指定节点的最近公共祖先
我们来进行思路梳理🤔🤔🤔
- 首先的话就是找最近公共祖先我们需要从底向上遍历二叉树，所以只能通过后序遍历（左右中）来实现从底向上遍历🤔🤔🤔
递归函数返回值 递归函数（递归参数给定节点p,递归参数给定节点q,递归参数二叉树根节点root）{
//递归出口
//处理左子树
//处理右子树
//处理中间父结点
}
-
接着的话最重要的就是怎么判断中间父结点是不是给定节点p和q的最近公共祖先呢🤔🤔🤔，如果左子树与右子树分别找到q/p则当前root就是最近的公共祖先
-
那有人会说了如果root是q/p呢，这个就属于递归出口的判断逻辑了，首先我们会判断每个节点也必然会进行空节点判断所以递归出口有
if(root == null)return null;，如果root为q/p那么也得返回找到的root节点然后呢？🤔🤔🤔接着往其左右子树去找剩下的节点能不能找到
TreeNode 递归函数（递归参数给定节点p,递归参数给定节点q,递归参数二叉树根节点root）{
if(root == q || root == p || root == null) return root;//递归出口
//处理左子树
//处理右子树
//处理中间父结点
}
思路梳理完毕后我们来紧接着梳理递归三要素🤔🤔🤔
- 确定递归函数的参数和返回值
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {}
- 确定递归出口
if(root == q || root == p || root == null) return root;
- 确定递归的单层处理逻辑
/**单层处理逻辑 */
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);//后序遍历
if(left != null && right != null) return root;
if(left == null) return right;
return left;
递归法java代码如下
/**递归法 */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == q || root == p || root == null) return root;
/**单层处理逻辑 */
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);//后序遍历
if(left != null && right != null) return root;
if(left == null) return right;
return left;
}
}
我们接着来梳理迭代法的思路🤔🤔🤔
- 我们可以利用栈进行深度优先搜索来遍历二叉树，同时记录每个节点的父结点信息以便在找到p/q节点时能够追溯路径🤔🤔🤔
HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();//哈希表存储每个节点的父节点
- 找到p和q节点时遍历其中一个节点的路径，返回第一个相交的节点作为最近公共祖先🤔🤔🤔
HashSet<TreeNode> ancestors = new HashSet<>();//准备处理p/q节点的全部父节点路径
while(p != null){ //列出p的所有祖先节点
ancestors.add(p);
p = parentMap.get(p);
}
while(!ancestors.contains(q)){//查找p的所有祖先节点中的第一个公共祖先
q = parentMap.get(q);
}
return q;
完整迭代法代码如下
/**迭代法 */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;//提前结束
HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();//哈希表存储每个节点的父节点
Stack<TreeNode> stack = new Stack<>();
stack.push(root);//准备前序遍历
parentMap.put(root, null); //根节点没有父结点
while(!parentMap.containsKey(q) || !parentMap.containsKey(p)){ //直到路径找到p和q
TreeNode cur = stack.pop();
if(cur.left != null){//处理左子树
parentMap.put(cur.left, cur);
stack.push(cur.left);
}
if(cur.right != null){//处理右子树
parentMap.put(cur.right, cur);
stack.push(cur.right);
}
}
HashSet<TreeNode> ancestors = new HashSet<>();//准备处理p/q节点的全部父节点路径
while(p != null){ //列出p的所有祖先节点
ancestors.add(p);
p = parentMap.get(p);
}
while(!ancestors.contains(q)){//查找p的所有祖先节点中的第一个公共祖先
q = parentMap.get(q);
}
return q;
}
二叉搜索树的最近公共祖先
LeetCode题目链接
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
我们来进行思路梳理🤔🤔🤔
-
首先的话就是找最近公共祖先我们需要从底向上遍历二叉树，所以只能通过后序遍历（左右中）来实现从底向上遍历，这个逻辑不变🤔🤔🤔
-
接着的话最重要的就是怎么判断中间父结点是不是给定节点p和q的最近公共祖先呢🤔🤔🤔，如果左子树与右子树分别找到q/p则当前root就是最近的公共祖先，对于二叉搜索树的话，根节点的值大于左子树的值小于右子树的值，所以我们可以得到要找的最近公共祖先就是数组在
[q.val, p.val]或者[p.val, q.val]之中
ok，我们直接梳理递归三要素
- 确定递归参数和返回值
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {}
- 确定递归出口
if(root == null) return root;
- 确定单层处理逻辑
if(root.val > q.val && root.val > p.val){
return lowestCommonAncestor(root.left, p, q);//往左找
} else if(root.val < q.val && root.val < p.val){
return lowestCommonAncestor(root.right, p, q);//往左找
}else{
return root;//找到了
}
总的递归代码如下
/**递归法 */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;
if(root.val > q.val && root.val > p.val){
return lowestCommonAncestor(root.left, p, q);//往左找
} else if(root.val < q.val && root.val < p.val){
return lowestCommonAncestor(root.right, p, q);//往左找
}else{
return root;//找到了
}
}
}
我们接着来梳理迭代法的逻辑🤔🤔🤔
- 由于二叉搜索树的性质，我们递归本质上是去找一个数值介于p与q数值之间的节点，所以我们迭代法无需栈或者队列来存储节点🤔🤔🤔
迭代法代码如下
/**迭代法 */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null){
if(root.val > q.val && root.val > p.val) {
root = root.left;
}else if(root.val < q.val && root.val < p.val){
root = root.right;
}else{
return root;
}
}
return null;
}
}
总结
国庆假期结束，开始加油啦✊✊✊
