左神算法新手班课程学习笔记07
纳西妲首席爹粉
2023-01-12 22:20
阅读2145
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
07 继续二叉树的很多题目
内容：
进一步讲解二叉树题目，来熟悉二叉树
题目：
1. 二叉树按层遍历并收集节点
Leetcode原题，https://leetcode.com/problems/binary-tree-level-order-traversal-ii
/*
建立一个新队列，队列长度作为循环的次数。先把根节点加入队列，然后进入循环。循环中，curNode先接受队列的弹出元素，把curNode的值添加到curAns中。如果curNode有左节点，将其左节点加入队列中，如果有右节点，将其右节点加入队列中。循环结束。将curAns加入到ans的头节点处。
*/
public List<List<Integer>> leverOrderBottom(TreeNode root){
List<List<Integer>> ans = new LinkedList<>();
if(root == null){
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> curAns = new LinkedList<>();
for(int i = 0; i < size; i++){
TreeNode curNode = queue.poll();
curAns.add(curNode.val);
if(curNode.left != null){
queue.add(curNode.left);
}
if(curNode.right != null){
queue.add(curNode.right);
}
}
ans.add(0,curAns);
}
return ans;
}
2. 判断是否是平衡二叉树
Leetcode原题，https://leetcode.com/problems/balanced-binary-tree
public static boolean isBalanced(TreeNode root){
return process(root).isBalanced;
}
//以某个节点为头节点时，给出两个信息：1）整棵树是否平衡 2）整棵树的高度是什么
public static class Info{
public boolean isBalanced;
public int height;
public Info(boolean i, int h){
isBalanced = i;
height = h;
}
}
public static Info process(TreeNode x){
if(x == null){
return new Info(true,0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height,rightInfo.height) +1;
boolean = isBalanced = leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height - rightInfo.height) <2;
return new Info(isBalanced,height);
}
3. 在二叉树上能否组成路径和
Leetcode原题，https://leetcode.com/problems/path-sum
//全局变量isSum;
public static boolean isSum = false;
public static boolean hasPathSum(TreeNode root, int sum){
if(root == null){
return false;
}
isSum = false;
process(root,0,sum);
return isSum;
}
public static void process(TreeNode x, int preSum, int sum){
//如果x为叶子节点
if(x.left == null && x.right == null){
if(x.val + preSum == sum){
isSum = true;
}
}
//如果x为非叶子节点
preSum += x.val;
if(x.left != null){
process(x.left, preSum, sum);
}
if(x.right != null){
process(x.right,preSum,sum);
}
}
4. 在二叉树上收集所有达标的路径和
Leetcode原题，https://leetcode.com/problems/path-sum-ii
public static List<List<Integer>> pathSum(TreeNode root, int sum){
List<List<Integer>> ans = new ArrayList<>();
if(root == null){
return ans;
}
ArrayList<Integer> path = new ArrayList<>();
process(root,path,0,sum,ans);
return ans;
}
public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans){
//叶子节点情况
if(x.left == null && x.right == null){
if(preSum + x.val == sum){
add.path(x.val);
ans.add(copy(path));
path.remove(path.size() -1);
}
return;
}
//非叶子节点
path.add(x.val);
preSum += x.val;
if(x.left != null){
process(x.left,path,preSum,sum,ans);
}
if(x.right != null){
process(x.right,path,preSum,sum,ans);
}
path.remove(path.size()-1);
}
public static List<Integer> copy(List<Integer> path){
List<Integer> ans = new ArrayList<>();
for(Integer num : path){
ans.add(num);
}
return ans;
}
5. 判断二叉树是否是搜索二叉树
//对于搜索二叉树，其中序遍历严格递增
public static class Info{
public boolean isBST;
public int max;
public int min;
public Info(boolean is, int ma, int mi){
isBST = is;
max = ma;
min = mi;
}
}
public static Info process(TreeNode x){
if(x == null){
return null;//max,min不能设置成0，root可能为负数
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.val;
int min = x.val;
if(leftInfo != null){
max = Math.max(leftInfo.max,max);
min = Math.min(leftInfo.min,min);
}
if(rightInfo != null){
max = Math.max(rightInfo.max,max);
min = Math.min(rightInfo.min,min);
}
boolean isBST = true;
if(leftInfo != null && !leftInfo.isBST){
isBST = false;
}
if(rightInfo != null && !rightInfo.isBST){
isBST = false;
}
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
if(!leftMaxLessX || !rightMinMoreX){
isBST = false;
}
return new Info(isBST,max,min);
}
//---------------------------------------
public static class Info {
public boolean isBST;
public int max;
public int min;
public Info(boolean is, int ma, int mi) {
isBST = is;
max = ma;
min = mi;
}
}
public static Info process(TreeNode x) {
if (x == null) {
return null;
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.val;
int min = x.val;
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
}
boolean isBST = false;
boolean leftIsBst = leftInfo == null ? true : leftInfo.isBST;
boolean rightIsBst = rightInfo == null ? true : rightInfo.isBST;
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
if (leftIsBst && rightIsBst && leftMaxLessX && rightMinMoreX) {
isBST = true;
}
return new Info(isBST, max, min);
}
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
Day 24✅ 今天做了：项目第九章部分⏰ 明天计划：要去招聘会看看，回来做完第九章📚 今日感悟：langsmith也挺重要啊这么看
0
Day 1✅ 今天做了：查看训练营阶段计划，AI第一章机器学习与深度学习理论基础阅读完毕，做了笔记⏰ 明天计划：第二章看完+做笔记，第一章复习📚 今日感悟：本科好多学过的内容，老师写的通俗易懂，以最简单的话语解释了一个个难理解的名词，相信以我之前的基础能完整理解概念，期待训练营结束的蜕变，坚持每日打卡。
1
day19现在学习好慢啊，有点焦虑，不知道怎么准备，现在把springboot的一部分知识补完了，后面自己要尝试把用户管理中心自己做出来了还要准备od算法题，虽然csp考过180，有了基础不是很难，但是还是要多看看不然会翻车。放三天假现在过了两天了，跑完跑去的学得好慢，加油，明天开始用户管理中心，争取下个星期自己独立完成
1
Day 26✅ 今天做了：1、扇贝英语单词打卡2、英语听说读写、听力练习3、微信阅读15分钟4、编程导航学习5、阅读 AI Agent 文献⏰ 明天计划：待定📚 今日感悟：Keep going！
1
Day 11✅ 今天做了：续上次完成了Ai智能体项目第二章视频学习，掌握了java中多种方式接入ai大模型，sdk、http、chatmodel等⏰ 明天计划：完成Ai智能体项目第三章上视频学习📚 今日感悟：掌握学习方式比掌握知识更重要，要学会查询管方文档
1
