第六章 二叉树part07
今日内容
● 530.二叉搜索树的最小绝对差
● 501.二叉搜索树中的众数
● 236.二叉树的最近公共祖先
详细布置
530.二叉搜索树的最小绝对差
需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接/文章讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html
视频讲解：https://www.bilibili.com/video/BV1DD4y11779
501.二叉搜索树中的众数
和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看，然后看我的视频讲解。
https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp
236. 二叉树的最近公共祖先
本题其实是比较难的，可以先看我的视频讲解
https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
●day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
●day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBHday21
搜索树的最小绝对差
递归法
遍历搜索树,双指针指向当前节点和上一个节点,更新差值;返回void
class Solution {
int mininum = Integer.MAX_VALUE;
TreeNode pre = null;
public int getMinimumDifference(TreeNode root) {
//搜索树最小的差值肯定在相邻节点之间,所以遍历一次就可以了
trversal(root);
return mininum;
}
private void trversal(TreeNode root){
if(root == null) return;
//要用到搜索树的特性必须中序遍历
trversal(root.left);
if(pre != null) mininum = Math.min(root.val - pre.val, mininum);
pre = root;
trversal(root.right);
}
}
搜索树中的众数
递归法
众数可能有多个,遍历搜索树,更新众数数组;返回void
要用到搜索树的特性,需要中序遍历让输出是从小到大,这样比较pre.val == cur.cal就知道重复了
class Solution {
List<Integer> result;
int maxcount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
result = new ArrayList<>();
maxcount = 0;
count = 0;
pre = null;
if( root == null) return null;
trversal(root);
int[] result1 = new int[result.size()];
for(int i = 0; i < result.size(); i++){
result1[i] = result.get(i);
}
return result1;
}
public void trversal(TreeNode root){
if( root == null) return;
trversal(root.left);
if( pre == null) count = 1;//遇到的是第一个节点,pre还是null呢
else if ( pre.val != root.val) count = 1;
else count++;
if(count == maxcount) result.add(root.val);
else if(count > maxcount){
result.clear();
result.add(root.val);
maxcount = count;
}
pre = root;
trversal(root.right);
}
}
二叉树的最近公共祖先
递归法
从下往上遍历,后续遍历,返回公共祖先节点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//因为牵扯到回溯所以后序遍历,遍历整棵树而不是一条边,所以left == XX,后面处理left和right,而不是if(leftXX) 就直接return
if( root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if( left != null && right == null) return left;
else if(left == null && right != null) return right;
else if(left != null && right != null) return root;
else{
return null;
}
}
}
小结:前中后序遍历好像有点明白咋回事了,没那么懵了;另外,看到一个训练营结营总结的帖子(附到链接里了),感觉特别好,最近也有类似的感受,激励自己也同时送给刚开始学算法的大家:
感谢大佬分享:
代码随想录-算法训练营day21【二叉树07：二叉搜索树的最小绝对差、二叉搜索树中的众数、二叉树的最近公共祖先】-CSDN博客