rtk建站教程,网站后台不能审核删除,商品营销推广的方法有哪些,多平台发布工具【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(二) 大家好 我是寸铁#x1f44a; 金三银四#xff0c;树、dfs、bfs、回溯、递归是必考的知识点✨ 快跟着寸铁刷起来#xff01;面试顺利上岸#x1f44b; 喜欢的小伙伴可以点点关注 #x1f49d; 上期回顾 感谢大家的支持 金三银四树、dfs、bfs、回溯、递归是必考的知识点✨ 快跟着寸铁刷起来面试顺利上岸 喜欢的小伙伴可以点点关注 上期回顾 感谢大家的支持 上期刷题笔记成功入选专栏第8名 【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(一) 话不多说开始新的篇章继续刷起来 124. 二叉树中的最大路径和
思路 要求返回其最大路径和 做法路径和枚举每个点作为起点,加上左右子树的值,取最大值即可。 先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。 回溯向上回溯时,会计算上层根节点的路径和,继续取一个最大值。 返回由于每个节点只能选一条路走最大路径和下应该选择左右分支的最大值分支 代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int maxSum Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {//递归函数入口maxGain(root);//返回最大路径和return maxSum;}//题意分析:/*要求返回其最大路径和做法路径和枚举每个点作为起点,加上左右子树的值,取最大值即可。先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。回溯向上回溯时,会计算上层根节点的路径和,继续取一个最大值。返回由于每个节点只能选一条路走最大路径和下应该选择左右分支的最大值分支*/public int maxGain(TreeNode node){if(node null){return 0;}//向左递归,计算左子树的叶子节点的最大路径和//如果小于0 则不选该分支 因为选了后路径和反而更小int leftGain Math.max(maxGain(node.left) , 0);//向右递归,计算右子树的叶子节点的最大路径和//如果小于0 则不选该分支 因为选了后路径和反而更小int rightGain Math.max(maxGain(node.right) , 0);//计算//回溯时会依次把上层非叶子节点做为根节点,计算其路径和int priceNewPath node.val leftGain rightGain;//把每次计算的结果取一个maxmaxSum Math.max(maxSum , priceNewPath);//返回一条较大路径 给上层节点继续计算路径和return node.val Math.max(leftGain , rightGain);}
}236. 二叉树的最近公共祖先
思路 核心思想 不断向上层返回递归左、右子树的结果 再根据结果是否存在p、q 确定返回的最近公共祖先 模拟分析图 代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {//核心思想//不断向上层返回递归左、右子树的结果//再根据结果是否存在p、q 确定返回的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//如果说根节点为空 则向上返回null即可if(root null)return null;//这里是针对两种情况//一种是递归遍历时,遍历到的节点为p或者q则向上返回root//一种是p为当前的根节点,q为p所在树的后面节点出现,则直接向上返回root即可if(root p || root q)return root;//左、右、中//后序遍历 根据递归搜索到的左、右子树节点的情况进行判断//递归左子树TreeNode left lowestCommonAncestor(root.left , p , q);//递归右子树 TreeNode right lowestCommonAncestor(root.right , p , q);//中的逻辑//如果说左子树和右子树不为空//则当前的root就是最近公共祖先//向上返回即可if(left ! null right ! null){return root;}else if(left ! null right null){//说明 左子树为最近公共祖先 向上返回return left;}else if(left null right ! null){//说明 右子树为最近公共祖先 向上返回return right;}else{return null;}}
} 102. 二叉树的层序遍历
考点
层序遍历、BFS
思路 思路借助队列实现层序遍历,维护一个节点队列,记录队列的长度。 每次只弹出这一层的节点,把弹出节点添加到结果队列中。 再把弹出节点的左孩子、右孩子添加到节点队列中。 用于下一次节点队列节点的遍历与弹出。 代码 class Solution {/*思路借助队列实现层序遍历,维护一个节点队列,记录队列的长度。每次只弹出这一层的节点,把弹出节点添加到结果队列中。再把弹出节点的左孩子、右孩子添加到节点队列中。用于下一次节点队列节点的遍历与弹出。*/public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if(root ! null){QueueTreeNodequeue new LinkedList();queue.offer(root);int size;TreeNode node;while(!queue.isEmpty()){ListIntegerans new ArrayList();size queue.size();while(size-- 0){node queue.poll();ans.add(node.val);if(node.left ! null)queue.offer(node.left);if(node.right ! null)queue.offer(node.right);}res.add(ans);}}return res;}
}199. 二叉树的右视图
考点
层序遍历、BFS
思路 遍历每一层节点时把他加入节点队列。获取当前队列的长度弹出节点时将其左右子孩子都加入队列中用于下一轮队列的弹出弹出最后一个节点时直接将该节点的值添加到结果队列。 代码 class Solution {public ListInteger rightSideView(TreeNode root) {//创建一个队列用于存储二叉树右视图节点的值ListInteger res new ArrayList();if(root ! null){//创建队列用于层序遍历(bfs),存入每一行的点QueueTreeNodequeue new LinkedList();//先把根节点添加到队列中queue.offer(root);//队列的大小,放到外面,减少内存开销。int size;//存储从队列弹出来的节点,用于把弹出节点的值写入res队列中。TreeNode node;while(!queue.isEmpty()){size queue.size();while(size -- 0){node queue.poll();//不知道右视图看到的节点情况//索性每次弹出节点时,把节点的左孩子和右孩子都添加到队列中。if(node.left ! null)queue.offer(node.left);if(node.right ! null)queue.offer(node.right);//由于是从左到右遍历,入队,最后一个节点为最右侧节点//弹出最后一个节点时,把节点的值添加到res中。//注意这里是size-- 当size为1时,即为最后一个节点,--后为0。if(size 0)res.add(node.val);}}}return res;}
}637. 二叉树的层平均值
考点
层序遍历、BFS
思路 思路遍历每一层的节点,将其子孩子添加到队列获取队列长度。 用临时变量计算每一层的节点的和值,再除以队列长度,最后添加到结果队列中即可。 代码 class Solution {/*思路遍历每一层的节点,将其子孩子添加到队列获取队列长度。用临时变量计算每一层的节点的和值,再除以队列长度,最后添加到结果队列中即可。*/public ListDouble averageOfLevels(TreeNode root) {ListDoubleres new ArrayList();if(root ! null){QueueTreeNodequeue new LinkedList();queue.offer(root);int size;TreeNode node;while(!queue.isEmpty()){double sum 0;size queue.size();for(int i 0; i size; i){node queue.poll();sum node.val; if(node.left ! null)queue.offer(node.left);if(node.right ! null)queue.offer(node.right);}res.add(sum / size);} }return res;}
}103. 二叉树的锯齿形层序遍历
考点
层序遍历、双端队列、BFS
思路 根据结果队列的层数如果说层数是偶数(层数从0开始)则进行从左到右遍历即头插。如果说层数是奇数(层数从0开始)则进行从右到左遍历即尾插。 代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger zigzagLevelOrder(TreeNode root) {QueueTreeNodequeue new LinkedList(); //维护一个队列,存储节点ListListIntegerres new ArrayList();//存储最后的结果if(root ! null){queue.offer(root);int size;TreeNode node;while(!queue.isEmpty()){//只有队列不为空的时候,再进行弹出队列的节点操作。size queue.size();//更新当前的队列size确定弹出当前多少个节点用于下一轮的更新。ListIntegerans new LinkedList();//存储这一层的节点while(size -- 0){node queue.poll();//弹出节点//如果说层数(从0开始)为偶数,则进行尾插,即从左到右if(res.size() % 2 0)ans.addLast(node.val);//否则,进行头插,则是从右到左else ans.addFirst(node.val);//把弹出节点的左、右孩子入队if(node.left ! null)queue.offer(node.left);if(node.right ! null)queue.offer(node.right);}res.add(ans);//添加ans到最后的结果队列res中}}return res;}
}
