左神算法新手班课程学习笔记07
纳西妲首席爹粉
2023-01-12 22:20
阅读2175
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
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 30✅ 今天做了：工程项目生成⏰ 明天计划：功能扩展📚 今日感悟：昨天休息玩去了。之前的nginx部署有点问题，今天搞了很久，项目部署我确实完全小白来着
0
Day 12✅ 今天做了：完成AI超级智能体项目3-4节⏰ 明天计划：完成AI超级智能体项目5-6节📚 今日感悟：掌握了基于SpringAI的Advisor使用、结构化输出、RAG基础等
1
Day 24✅ 今天做了：AI 面试通关120问。⏰ 明天计划：AI面试通关120问；简历优化。📚 今日感悟：AI 相关面试知识点基本熟知，仍需进一步巩固。
0
Day 37✅ 今天做了：1、扇贝英语单词打卡2、微信阅读15分钟3、英语听说读写4、编程导航学习⏰ 明天计划：待定📚 今日感悟：Keep going！
1
day26学了差不多一个月了，通过用户管理中心大概了解了java开发。后面了解，现在是ai时代了，很多程序员都用ai来编程了，甚至还有很多用ai编程的岗位。接下来这两天加上下一周完成ai超级智能体吧。感觉这个星期没干啥，也就部署了几个项目，学习ai知识，找找校招信息，用了几个ai工具，弄了一个云服务器。感觉有成果的是部署了一个用trae自动生成的用户管理中心当然只有后端，所以只能打开借口文档swa
4
