一文详解“二叉树中的深搜“在算法中的应用

ops/2024/12/26 2:41:57/

 找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏： 递归、搜索与回溯算法专题

目录

深搜的介绍

2331.计算布尔二叉树的值

129.求根节点到叶节点数字之和

814.二叉树剪枝

98.验证二叉搜索树

230.二叉搜索树中第K小的元素

257.二叉树的所有路径

 

深搜的介绍

深搜是深度优先遍历（深度优先搜索）的一种简称。那什么是深度优先遍历呢？对于单分支的情况来说，就是直接暴力遍历，例如，遍历顺序表、链表的情况。对于多分支的情况来说，深度优先遍历就是一条道走到黑（或者说不撞南墙不回头，但是撞了就立马回头），沿着某条路径一直走直至不能走下去了，再返回去沿着其他路径走，最典型的代表：二叉树中的前序遍历、中序遍历、后序遍历都是深度优先遍历的形式。因为不管是前序、中序、后序，它们都是沿着某条路线一直走到不能走了才返回。

接下来我们通过一些题目来认识"深搜"。

2331.计算布尔二叉树的值

题目：

给你一棵 完整二叉树 的根，这棵树有以下特征：

  • 叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
  • 非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算 一个节点的值方式如下：

  • 如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
  • 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。

返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

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

示例 1：

输入：root = [2,1,3,null,null,0,1]
输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。

示例 2：

输入：root = [0]
输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

  • 树中节点数目在 [1, 1000] 之间。
  • 0 <= Node.val <= 3
  • 每个节点的孩子数为 0 或 2 。
  • 叶子节点的值为 0 或 1 。
  • 非叶子节点的值为 2 或 3 。

思路：要知道整棵树的布尔值，得先知道其左子树与右子树的布尔值，然后再通过根结点的运算符来计算最终的结果，而想知道左子树的布尔值，还得知道其左子树与右子树的布尔值，然后再通过左子树的运算符来计算。这里我们已经找到了重复子问题了（针对二叉树的问题，是很容易就找到重复子问题）。

代码实现：

java">class Solution {// 计算出root指针指向的树的布尔值public boolean evaluateTree(TreeNode root) {if (root.left == null && root.right == null) { // 叶子结点return root.val == 1 ? true : false;}// 先得计算出左子树boolean left = evaluateTree(root.left);// 再去计算右子树boolean right = evaluateTree(root.right);// 再根据根结点的值来计算出最终结果if (root.val == 2) { // orreturn left || right;} else { // andreturn left && right;}}
}

这里其实就是一个后序遍历。

129.求根节点到叶节点数字之和

题目： 

 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2代表数字 12从根到叶子节点路径 1->3代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5代表数字 495
从根到叶子节点路径 4->9->1代表数字 491
从根到叶子节点路径 4->0代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

  • 树中节点的数目在范围 [1, 1000] 内
  • 0 <= Node.val <= 9
  • 树的深度不超过 10

思路：

代码实现：

java">class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}private int dfs(TreeNode root, int prevSum) {// 把当前路径的值计算出来prevSum = prevSum * 10 + root.val;// 判断当前结点是否为叶子结点if (root.left == null && root.right == null) {return prevSum;}// 可能会存在左子树为空，右子树不为空；左子树不为空，右子树为空的情况// 这里没有去判断当前结点是否为null的情况，可能会出现空指针异常int sum = 0;if (root.left != null) {sum += dfs(root.left, prevSum);}if (root.right != null) {sum += dfs(root.right, prevSum);}return sum;}
}

814.二叉树剪枝

题目：

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：

输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]

示例 3：

输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]

提示：

  • 树中节点的数目在范围 [1, 200] 内
  • Node.val 为 0 或 1

思路：题目这里是让我们将二叉树中只包含数值0的结点的所在的子树给剪枝，也就是删除（置为null即可）。这里要删除就得判断其左子树是否符合只包含0，其右子树是否符合只包含0，并且当前结点的值是0，如果是的话，就得将这棵树删除，也就是置为null。

代码实现：

java">class Solution {// 函数的意义：给你一个根结点，把根结点所指向的树中只有0的子树给去除public TreeNode pruneTree(TreeNode root) {// 递归的出口if (root == null) {return null;}// 处理左子树TreeNode left = pruneTree(root.left);// 如果左子树为null，就得"剪枝"if (left == null) {root.left = null;}// 处理右子树TreeNode right = pruneTree(root.right);// 如果右子树为null，就得"剪枝"if (right == null) {root.right = null;}// 处理当前结点if (left == null && right == null && root.val == 0) {return null;}return root;}
}

98.验证二叉搜索树

题目：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

思路：本题就是让我们想办法证明这棵二叉树是二叉搜索树。很简单，二叉搜索树的性质：中序遍历二叉树，最终的序列是有序的。因此可以直接用一个数组暴力存储所有的值，然后去判断该数组是否有序即可。暴力方法虽然行得通，但还可以优化，我们要证明有序的话，可以用一个变量来记录前一个位置的值，当前一个位置的值小于当前位置的时候，说明是满足二叉搜索树的性质，那就继续判断下去，而如果不满足的话，那就直接返回false即可。最终遍历完成并未返回false，说明这棵树确实是二叉搜索树。

代码实现：

暴力解法：

java">class Solution {int[] nums;int i = 0;public boolean isValidBST(TreeNode root) {nums = new int[100001];// 中序遍历判断是否为有序序列即可dfs(root);for (int j = 0; j < i; j++) {if (j+1 < i && nums[j] >= nums[j+1]) {return false;}}return true;}void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);nums[i++] = root.val;dfs(root.right);}
}

优化解法：

java">class Solution {    // 使用一个变量来记录中序遍历的前一个数值long prev = Long.MIN_VALUE;// 函数的意义：给你一个root，判断其指向的树是否为二叉搜索树public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 判断左子树是否为二叉搜索树boolean left = isValidBST(root.left);if (!left) { // 如果为false，那么后面的就不需要判断了return false;}// 判断当前结点是否符合二叉搜索树的定义if (root.val > prev) {prev = root.val;} else {return false;}// 判断右子树是否为二叉搜索树boolean right = isValidBST(root.right);if (!right) { // 如果为false，那么后面的就不需要判断了return false;}return true;}
}

230.二叉搜索树中第K小的元素

题目：

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

思路：这一题本质上与上一题是差不多的，还是利用二叉搜索树的性质来解题。暴力解法就是中序遍历遍历整个二叉搜索树，将节点存储起来，然后返回第k-1个元素即可。优化的话，就是使用两个全局变量：一个去记录k的值，一个去记录最终返回的结果。

代码实现：

暴力解法：

java">class Solution {// 用一个数组将二叉搜索树的中序遍历存储起来int[] nums;int i;public int kthSmallest(TreeNode root, int k) {nums = new int[10001];i = 0;dfs(root);return nums[k-1];}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);nums[i++] = root.val;dfs(root.right);}
}

优化解法：

java">class Solution {// 函数的意义：找到root树的第k小的结点int count, ret;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}private void dfs(TreeNode root) {if (root == null || count == 0) {return;}dfs(root.left);if (--count == 0) {ret = root.val;return;}dfs(root.right);}
}

257.二叉树的所有路径

题目：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

  • 树中节点的数目在范围 [1, 100] 内
  • -100 <= Node.val <= 100

思路：题目是让我们将根结点到每个叶子结点的路径统计出来。其实也是比较简单的，只需要用一个字符串变量来记录当前的元素信息，如果是叶子结点的话，就存储到 List 中，反之则继续向下探索。

代码实现：

java">class Solution {List<String> l;public List<String> binaryTreePaths(TreeNode root) {l = new LinkedList<>();StringBuilder path = new StringBuilder();dfs(root, path);return l;}private void dfs(TreeNode root, StringBuilder _path) {// 新创建一个path变量，虽然值一样，但是地址并不一样// 这样每次在递归修改的时候，并不会相互影响，而是自己新创建的对象StringBuilder path = new StringBuilder(_path);if (root.left == null && root.right == null) {path.append(root.val);l.add(path.toString());return;} else {path.append(root.val);path.append("->");}if (root.left != null) {dfs(root.left, path);}if (root.right != null) {dfs(root.right, path);}}
}

注意：这里在统计完叶子结点之后，回溯的过程中，之前的 StringBuilder 变量已经发生了变化，并不是我们第一次来时的摸样了，这就需要我们去还原刚开始的样子，可以在每递归一次的时候，就去创建一个新的变量来记录当前的变化情况。 


http://www.ppmy.cn/ops/145005.html

相关文章

nginx(openresty) lua 解决对接其他平台，响应文件中地址跨域问题

nginx(openresty) lua 解决对接其他平台，响应文件中地址跨域问题

location 添加配置 # location 添加的配置 # 作用&#xff1a;清空body体中的内&#xff0c;使得在lua处理响应体是&#xff0c;重新计算返回大小【如果不置空&#xff0c;它会保留原始响应体大小&#xff0c;导致处理数据的时候出现截断的问题】 header_filter_by_lua ngx.h…
阅读更多...
Hive SQL 之 `LATERAL VIEW EXPLODE` 的正确打开方式

Hive SQL 之 `LATERAL VIEW EXPLODE` 的正确打开方式

一文彻底搞懂 LATERAL VIEW EXPLODE 1. 引言 在处理复杂数据结构&#xff08;如数组、映射&#xff09;时&#xff0c;Hive SQL 提供了强大的功能来简化查询和数据分析。其中&#xff0c;LATERAL VIEW 和 EXPLODE 是两个特别有用的关键字&#xff0c;它们可以帮助我们将复杂的…
阅读更多...
短视频运营行业该如何选择服务器？

短视频运营行业该如何选择服务器？

在互联网快速发展的时代&#xff0c;短视频行业也应运而生&#xff0c;企业为了保证用户能够浏览流畅且稳定的短视频&#xff0c;则需要选择一台合适的服务器来运行相关业务&#xff0c;本文就来探讨一下短视频运营行业该如何选择服务器吧&#xff01; 短视频行业一般需要处理大…
阅读更多...
迈向未来：.NET技术的持续创新与发展前景

迈向未来：.NET技术的持续创新与发展前景

随着信息技术的飞速发展&#xff0c;编程语言和开发框架不断涌现&#xff0c;许多技术平台以其独特的优势赢得了开发者的青睐。在这场技术的竞争中&#xff0c;.NET平台凭借其卓越的性能、广泛的生态系统以及持续创新的精神&#xff0c;成为了全球开发者的重要选择。本文将探讨…
阅读更多...
pycharm debug代码跳到c盘的一个临时文件夹里

pycharm debug代码跳到c盘的一个临时文件夹里

问题&#xff1a;在pycharm debug代码时跳到c盘的一个临时文件夹里。 解决方法&#xff1a; 即使是在tools的develop里面填好mapping了&#xff0c;也必须在debug的设置里面填好mapping。
阅读更多...
防抖、幂等和防超卖

防抖、幂等和防超卖

防抖和幂等 接口防抖&#xff08;Debounce&#xff09;和幂等是两个不同的概念&#xff0c;但它们确实在某些场景下可以达到类似的效果&#xff0c;都旨在避免多次重复操作造成的问题。 防抖的主要目的是控制高频操作的触发&#xff0c;确保在一定时间间隔内只执行一次请求。…
阅读更多...
React+TypeScript+Tailwind 实现圣诞祝福网页

React+TypeScript+Tailwind 实现圣诞祝福网页

圣诞节快要到啦&#xff0c;提前祝大家圣诞节快乐&#xff01;&#xff01;&#xff01; 项目完整源码在最后哦✨ 视频 &#xff08;一&#xff09;&#xff1a;项目环境搭建 在这个教程中&#xff0c;我们将一步步创建一个精美的圣诞祝福网页。本文是系列的第一部分&#xf…
阅读更多...
【LuaFramework】服务器模块相关知识

【LuaFramework】服务器模块相关知识

目录 一、客户端代码 二、本地服务器代码 三、解决服务器无法多次接收客户端消息问题 一、客户端代码 连接本地服务器127.0.0.1:2012端口&#xff08;如何创本地服务器&#xff0c;放最后说&#xff09;&#xff0c;连接成功后会回调 协议号Connect是101&#xff0c;其他如下…
阅读更多...
最新文章

Copyright @ 2022~2023