左神算法新手班课程学习笔记07
纳西妲首席爹粉
2023-01-12 22:20
阅读2241
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
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个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
想请教一下大家最近这几年什么岗位比较适合就业啊，我现在是杭电研一，目前也比较迷茫，从学长那里了解到的就业情况也不是很友好，希望在杭州能找个工资不错的工作，请问我现在应该往什么方向的岗位努力合适一点呢？
1
Day 1✅ 今天做了：记忆10个面试题知识点内容⏰ 明天计划：晚上继续坚持学习
0
Day 57✅ 今天做了：简历投递；实习项目面试问答；力扣HOT100。⏰ 明天计划：简历投递；面经拷打；力扣HOT100。📚 今日感悟：今日简历投递数较少，项目复盘和投递需同步推进。
1
Day 28✅ 今天做了：Redisson分布式锁⏰ 明天计划：秒杀优化📚 今日感悟：讲源码太困了, 跳跳跳跳
0
先有企业级代码思维（代码写健壮），再有企业级代码
0
