左神算法新手班课程学习笔记07
纳西妲首席爹粉
2023-01-12 22:20
阅读2225
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
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 84✅ 今天做了：1.尝试skill一些重复性的工作2.复习3.项目⏰ 明天计划：1.项目2.有时间再复习📚 今日感悟：还是想的太多做的太少，以至于想只导致浪费了更多时间也不是一天两天的事了，但居家太久导致问题更明显了。希望调整好的时候也差不多找到新工作吧
2
Day 25✅ 今天做了：Agent 权限⏰ 明天计划：MCP📚 今日感悟：今天结束了 Agent 权限这一章节， 加入了限流、异步任务和增量检索这几个功能
1
day66✅今天做了:看八股，梳理学习项目，看话术，leetcode3道⏰明天计划:休息，准备整理一下行李，过几天回家
1
Day 47✅ 今天做了：完成开始AI-Python章节Agentic RAG项目第7节、leetcode hot100刷题、Python基础知识面试题准备、AI速记120问复习⏰ 明天计划：开始AI-Python章节Agentic RAG项目第8节、leetcode hot100刷题、Python基础知识面试题准备、AI速记120问复习📚 今日感悟：继续加油
3
完成AI 万能视频下载总结器项目！---总耗时30h,第一次用ai完成项目，使用Qoder+Qwen3.8-Max实现。已部署上线（没有完全上线好，买错服务器了🤣，不能备案，所以支付功能用不了，等有钱再买个新的服务器）也上传了github，话说这个千问只能看到Credits 消耗都不知道到底用了多少token
7
