代码随想录-Day18

2024-05-25 19:04
文章标签 随想录 代码 day18

本文主要是介绍代码随想录-Day18,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

方法一:深度优先搜索

class Solution {int curVal = 0;int curHeight = 0;public int findBottomLeftValue(TreeNode root) {int curHeight = 0;dfs(root, 0);return curVal;}public void dfs(TreeNode root, int height) {if (root == null) {return;}height++;dfs(root.left, height);dfs(root.right, height);if (height > curHeight) {curHeight = height;curVal = root.val;}}
}

这段代码是用来解决一个问题:在一棵二叉树中找到最底层最左边的节点的值。代码采用了深度优先搜索(DFS)的方式遍历二叉树,并利用两个类变量curValcurHeight记录当前遍历到的最深的节点值以及相应的深度。

  • class Solution 是定义的解题类。

  • int curVal = 0;int curHeight = 0; 是类变量,分别用来存储当前已知的最深节点的值和其所在深度。

  • public int findBottomLeftValue(TreeNode root) 是主方法,输入为二叉树的根节点 root,输出是最底层最左边节点的值。这里定义了一个局部变量 curHeight 来记录当前遍历的深度,虽然它与类变量同名,但在方法作用域内互不影响。首先调用 dfs 方法对树进行深度优先遍历,并传入根节点和初始高度0。遍历完成后,返回类变量 curVal 作为结果。

  • public void dfs(TreeNode root, int height) 是一个私有的辅助方法,用于递归地进行深度优先遍历。输入参数为当前节点 root 和该节点的当前高度 height

    • 如果节点为空,则直接返回,结束本次递归。
    • 然后将高度加1,准备遍历下一层。
    • 先递归遍历左子树,再递归遍历右子树,这样的顺序保证了在遍历到同一深度的节点时,先访问左边的节点。
    • 在递归调用返回之后,检查当前节点的高度是否大于已知的最大深度 curHeight。如果是,则更新 curHeightcurVal,使得它们分别记录当前遍历到的最深深度及该深度最左边节点的值。

通过这样的DFS遍历,能够确保最后得到的 curVal 是位于最底层最左边的节点的值。

方法二:广度优先搜索

class Solution {public int findBottomLeftValue(TreeNode root) {int ret = 0;Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {TreeNode p = queue.poll();if (p.right != null) {queue.offer(p.right);}if (p.left != null) {queue.offer(p.left);}ret = p.val;}return ret;}
}

这段代码实现了在二叉树中找到最底层最左边的节点值。代码使用了广度优先搜索(BFS)进行层次遍历。以下是代码的详细解释:

方法签名

public int findBottomLeftValue(TreeNode root)

该方法接受一个 TreeNode 类型的根节点 root 作为输入,返回一个整数类型的最底层最左边的节点值。

变量声明

int ret = 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
  • ret 变量用于存储最终的最底层最左边的节点值。
  • queue 是一个队列,用于执行广度优先搜索。初始化为 ArrayDeque 类型。

初始化队列

queue.offer(root);

将根节点 root 放入队列中。

广度优先搜索

while (!queue.isEmpty()) {TreeNode p = queue.poll();if (p.right != null) {queue.offer(p.right);}if (p.left != null) {queue.offer(p.left);}ret = p.val;
}
  • 使用 while 循环,当队列不为空时继续循环。
  • TreeNode p = queue.poll(); 取出队列的第一个节点 p
  • 如果 p 的右子节点不为空,将其放入队列。
  • 如果 p 的左子节点不为空,将其放入队列。
  • 每次循环,将当前节点的值 p.val 赋值给 ret

返回结果

return ret;

返回 ret 作为最底层最左边的节点值。

代码逻辑

  1. 初始化:将根节点放入队列中。
  2. 广度优先搜索
    • 每次从队列中取出一个节点。
    • 优先将右子节点入队,再将左子节点入队。
    • 更新 ret 为当前节点的值。
  3. 终止条件:当队列为空时,循环结束。此时,ret 存储的就是最底层最左边的节点值。

思路解释

使用广度优先搜索遍历树的每一层,并且每次都优先处理右子节点。这意味着当到达最底层时,最先被处理的节点将是最左边的节点。每次更新 ret,最终 ret 会是最底层最左边的节点值。

示例

考虑如下二叉树:

        2/ \1   3/ \4   5/7
  • 初始时,队列为 [2]
  • 取出 2,加入 31,队列为 [3, 1]
  • 取出 3,队列为 [1]
  • 取出 1,加入 54,队列为 [5, 4]
  • 取出 5,队列为 [4]
  • 取出 4,加入 7,队列为 [7]
  • 取出 7,队列为空

最终返回 7,即最底层最左边的节点值。

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

方法一:广度优先搜索

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}Queue<TreeNode> queNode = new LinkedList<TreeNode>();Queue<Integer> queVal = new LinkedList<Integer>();queNode.offer(root);queVal.offer(root.val);while (!queNode.isEmpty()) {TreeNode now = queNode.poll();int temp = queVal.poll();if (now.left == null && now.right == null) {if (temp == sum) {return true;}continue;}if (now.left != null) {queNode.offer(now.left);queVal.offer(now.left.val + temp);}if (now.right != null) {queNode.offer(now.right);queVal.offer(now.right.val + temp);}}return false;}
}

这段代码实现了一个名为 Solution 的类,其中有一个方法 hasPathSum,用于判断一棵二叉树中是否存在从根节点到叶子节点的路径,使得沿途经过的节点值之和等于给定的 sum 值。该方法采用了广度优先搜索(BFS)的策略,使用两个队列分别存储待遍历的节点和对应节点值的累加和。

  • 方法签名:public boolean hasPathSum(TreeNode root, int sum),接收二叉树的根节点 root 和目标和 sum,返回值是一个布尔值,表示是否存在满足条件的路径。

  • 初始化两个队列:Queue<TreeNode> queNode 用于存储待遍历的节点,Queue<Integer> queVal 用于存储从根节点到当前节点路径上节点值的累加和。首先将根节点和其值入队。

  • 使用 while 循环处理队列,直到队列为空,表示树已被完全遍历。

    • 每次循环从队列中弹出一个节点 now 和对应的累加和 temp
    • 判断当前节点是否为叶子节点(即左右子节点均为 null),若是且累加和 temp 等于目标和 sum,则返回 true,表示找到了满足条件的路径。
    • 若当前节点不是叶子节点,将其左右子节点(若存在)及其对应的累加和(子节点值加 temp)分别入队,以便下一轮循环继续遍历。
  • 如果循环结束还没有找到满足条件的路径,则返回 false

需要注意的是,这段代码的逻辑是正确的,但是它解决的问题是“是否存在从根节点到叶子节点的路径,其节点值之和等于给定的 sum”,而不是原问题描述中寻找二叉树中最底层最左边的节点值。对于后者,应该采用不同的逻辑来追踪每一层的第一个节点。

方法二:递归

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

这段代码是使用递归方法实现的 Java 程序,用于解决“判断一棵二叉树中是否存在从根节点到叶子节点的路径,使得沿途经过的节点值之和等于给定的 sum”的问题。这里是针对原始问题的正确解答,与之前讨论的寻找最底层最左边节点值的问题无关。下面是代码的详细解释:

  • Solution 中定义了方法 hasPathSum,它接收两个参数:一个 TreeNode 类型的参数 root 表示二叉树的根节点,一个整型参数 sum 表示目标和。

  • 首先,检查根节点是否为空,如果为空则直接返回 false,表示不存在这样的路径。

  • 然后,检查当前节点是否为叶子节点(即没有左右子节点)。如果是叶子节点,并且该节点的值等于 sum,则返回 true,表示找到了一条满足条件的路径。

  • 如果当前节点不是叶子节点,递归地在左子树和右子树中寻找满足条件的路径。这里通过减去当前节点的值 root.val 来更新目标和 sum,分别对左子树和右子树调用 hasPathSum 方法。如果左子树或右子树中任意一侧存在满足条件的路径,就返回 true;如果两侧都没有满足条件的路径,则返回 false

通过这种方式,代码高效地遍历了整棵树,仅沿着有可能达到目标和的路径进行探索,最终确定是否存在满足条件的路径。这是一种典型的深度优先搜索(DFS)策略。

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
在这里插入图片描述

方法一:递归

class Solution {int post_idx;int[] postorder;int[] inorder;Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();public TreeNode helper(int in_left, int in_right) {// 如果这里没有节点构造二叉树了,就结束if (in_left > in_right) {return null;}// 选择 post_idx 位置的元素作为当前子树根节点int root_val = postorder[post_idx];TreeNode root = new TreeNode(root_val);// 根据 root 所在位置分成左右两棵子树int index = idx_map.get(root_val);// 下标减一post_idx--;// 构造右子树root.right = helper(index + 1, in_right);// 构造左子树root.left = helper(in_left, index - 1);return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {this.postorder = postorder;this.inorder = inorder;// 从后序遍历的最后一个元素开始post_idx = postorder.length - 1;// 建立(元素,下标)键值对的哈希表int idx = 0;for (Integer val : inorder) {idx_map.put(val, idx++);}return helper(0, inorder.length - 1);}
}

这段代码是用于根据给定的中序遍历(inorder)和后序遍历(postorder)数组重建一棵二叉树。代码定义了一个名为 Solution 的类,其中有两个成员变量和两个主要方法:

  1. 成员变量:

    • post_idx:记录当前处理的后序遍历数组中的元素位置。
    • postorderinorder:分别存储给定的后序遍历和中序遍历数组。
    • idx_map:一个哈希映射,存储中序遍历中每个元素对应的索引,便于快速查找。
  2. 主要方法:

    • helper(int in_left, int in_right):这是一个递归方法,用于根据给定的中序遍历区间 [in_left, in_right] 重建子树。方法内部首先判断区间有效性,然后根据后序遍历数组的当前元素(即子树根节点)分割中序遍历区间,递归地构建右子树和左子树,最后返回根节点。

    • buildTree(int[] inorder, int[] postorder):这是主要的接口方法,接收中序遍历和后序遍历的数组,初始化必要的数据,包括设置 post_idx 初始值、构建哈希映射 idx_map,然后调用 helper 方法从整个中序遍历区间开始重建二叉树,并返回根节点。

整体逻辑遵循二叉树后序遍历的特性,即后序遍历的最后一个元素是树的根节点,利用中序遍历来确定左右子树的划分。通过哈希表快速定位根节点在中序遍历中的位置,以此分治递归地构建整颗二叉树。

方法二:迭代

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder == null || postorder.length == 0) {return null;}TreeNode root = new TreeNode(postorder[postorder.length - 1]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = inorder.length - 1;for (int i = postorder.length - 2; i >= 0; i--) {int postorderVal = postorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.right = new TreeNode(postorderVal);stack.push(node.right);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex--;}node.left = new TreeNode(postorderVal);stack.push(node.left);}}return root;}
}

这段代码实现了一个名为 Solution 的类,其中包含一个方法 buildTree,该方法接收两个整型数组参数 inorderpostorder,分别表示某个二叉树的中序遍历和后序遍历结果。目的是根据这两个遍历结果重建出原来的二叉树结构,并返回该二叉树的根节点。

代码逻辑分析如下:

  1. 首先检查 postorder 数组是否为空或者长度为0,如果是,则直接返回 null,表示没有树可构建。
  2. 初始化根节点:根据后序遍历特点,最后一个元素是树的根节点,所以创建一个新的 TreeNode,其值为 postorder 数组的最后一个元素。
  3. 准备一个 Deque(双端队列)stack,并把根节点压入栈中。
  4. 初始化 inorderIndexinorder 数组的最后一个有效索引,因为在后序遍历中根节点之后的元素将构成右子树或左子树。
  5. postorder 数组的倒数第二个元素开始遍历(索引 ipostorder.length - 20):
    • 获取当前遍历到的后序遍历值 postorderVal
    • 检查栈顶元素(即当前正在构建的子树的根节点)的值是否与 inorder[inorderIndex] 匹配:
      • 如果不匹配,说明当前 postorderVal 应该属于栈顶节点的右子树,因此创建一个新的右子节点,将其值设为 postorderVal,并压入栈中。
      • 如果匹配,说明已经处理完栈顶节点的右子树,需要向上回溯到可以连接新节点(当前 postorderVal 对应节点)作为左子节点的位置。通过一个 while 循环不断弹出栈顶节点并更新 inorderIndex,直到找到合适的位置(或栈为空)。
        • 找到合适位置后,为当前 node 创建左子节点,值为 postorderVal,并将其压入栈中,继续处理下一个 postorder 中的元素。
  6. 遍历完成后,栈中构建的结构即为完整的二叉树,返回根节点。

这种方法利用了后序遍历(左右根)和中序遍历(左根右)的特点,通过栈来辅助构建二叉树,从后序遍历数组反向构建,有效地恢复了原二叉树的结构。

这篇关于代码随想录-Day18的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1002356

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can