代码随想录day21 | leetcode 669.修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 二叉树总结篇

devtools/2024/12/23 5:20:25/

669.修剪二叉搜索树

调用递归实现剪枝

java">class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;if(root.val < low) return trimBST(root.right, low, high);  //如果当前节点的值小于low,意味着当前节点及其左子树中的所有节点都小于low,不符合要求。这时,应该跳过当前节点和左子树,递归处理右子树if(root.val > high) return trimBST(root.left, low, high); //同理root.left = trimBST(root.left, low, high); //修剪的目的是删除不在[low, high]范围内的节点 当某个节点不在范围内时,我们选择跳过该节点,并根据其值选择保留左子树或右子树。root.right = trimBST(root.right, low, high); return root;}
}
1. 当前节点值小于 low
java">if(root.val < low) return trimBST(root.right, low, high);
  • 如果当前节点的值小于 low,意味着当前节点及其左子树中的所有节点都小于 low,不符合要求。
  • 这时,应该跳过当前节点和左子树,递归处理右子树。
  • 返回右子树的修剪结果作为新的子树。
2. 当前节点值大于 high
java">if(root.val > high) return trimBST(root.left, low, high);
  • 如果当前节点的值大于 high,意味着当前节点及其右子树中的所有节点都大于 high,不符合要求。
  • 这时,应该跳过当前节点和右子树,递归处理左子树。
  • 返回左子树的修剪结果作为新的子树。
3. 当前节点符合范围
java">root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
  • 如果当前节点的值在 [low, high] 范围内,保留当前节点。
  • 对当前节点的左子树和右子树分别递归调用 trimBST,修剪它们。
  • 将修剪后的左子树和右子树分别赋值给 root.leftroot.right
  • 返回当前节点 root

108.将有序数组转换为二叉搜索树

左闭右闭 左等于右合法

java">class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traveal(nums, 0, num.length);}public TreeNode traveal(int[] nums, left, right) {//左闭右开   if(left >= right) return null;   //left > righ 左闭右闭int mid = (left + right) / 2;  //int mid = left + ((right - left) >> 1); 改进版TreeNode root = new TreeNode(nums[mid]);  //创建二叉搜索树的根节点root.left = traveal(nums, left, mid);  //(nums, left, mid - 1) 左闭右闭root.right = traveal(nums, mid + 1,right) //(nums, mid + 1, right) 左闭右闭return root;}
}

538.把二叉搜索树转换为累加树

java">class Solution {//双指针 累加前面的题有这样的写法int pre = 0;public TreeNode convertBST(TreeNode cur) {if(cur == null) return null;convertBST(cur.right);  cur.val += pre;pre = cur.val;convertBST(cur.left);return cur;}   
}

为什么用反中序遍历?

1. 二叉搜索树的性质:

  • 在中序遍历中,BST 的节点值是从小到大的顺序。
  • 反中序遍历(右-根-左)则是从大到小的顺序。

2. 累加树的构建规则:

  • 计算累加和时,需要从最大的节点开始累加。
  • 依次向前,当前节点的值加上之前所有节点的累加和(即 pre 变量),再将结果赋给当前节点。

二叉树总结篇

大体分分类

  • 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。
  • 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。
  • 求二叉搜索树的属性,一定是中序了,运用有序性了。

注意在普通二叉树的属性中,我用的是一般为后序,例如单纯求深度就用前序,leetcode257.找所有路径也用了前序,这是为了方便让父节点指向子节点。

在这里插入图片描述


http://www.ppmy.cn/devtools/144593.html

相关文章

相机内外参知识

已知相机的内外参数矩阵&#xff0c;可以求得相机在世界坐标系下的原点坐标。这里需要理解几个概念&#xff1a; 内参数矩阵&#xff08;Intrinsic Matrix&#xff09;: 描述相机本身的属性&#xff0c;比如焦距、主点位置等。外参数矩阵&#xff08;Extrinsic Matrix&#xf…

跟着问题学18——transformer模型详解及代码实战(3)Encode编码器

跟着问题学18——transformer模型详解及代码实战&#xff08;1&#xff09; 跟着问题学18——transformer详解(2)多头自注意力机制-CSDN博客 2.3 残差连接 通过自注意力层我们挖掘提取了原始数据的特征&#xff0c;但编码层中会有多个编码器&#xff0c;这会导致网络层数的加…

火山引擎FORCE:智算能力全面升级

火山引擎智算专场 &#xff1a; 有幸参加 2024年 12月18日 在 上海国际博览中心 15&#xff1a;00~17&#xff1a;00的 智算专场。 这里 火山引擎智算专场图片 &#xff1a; 火山引擎智算专场内容 &#xff1a; 火山引擎图片 智算专场&#xff1a;乘云之势&#xff0c;智启未…

Java中ArrayList和LinkedList的区别?

在 Java 中&#xff0c;ArrayList和LinkedList都是实现了List接口的集合类&#xff0c;用于存储和操作有序的元素集合。它们在内部实现和性能特性上存在一些显著的区别&#xff0c;以下是对这两者的详细比较&#xff1a; 底层数据结构 ArrayList&#xff1a;基于数组实现&…

android studio更改应用图片,和应用名字。

更改应用图标&#xff0c;和名字 先打开AndroidManifest.xml文件。 更改图片文件名字&#xff08; 右键-->构建-->重命名&#xff08;R&#xff09;&#xff09;

html 中 表格和表单的关系与区别

在 HTML 中&#xff0c;表格 (<table>) 和表单 (<form>) 是两种常用于展示数据和收集用户输入的元素。它们具有不同的功能和结构。以下是关于这两者的详细介绍&#xff1a; 1. HTML 表格&#xff08;<table>&#xff09; 表格用于展示结构化的数据&#xf…

Libevent实现TCP客户端服务器

Libevent实现TCP客户端服务器 17-libevent实现Tcp服务器流程_bilibili_哔哩哔哩_bilibili 文章目录 Libevent实现TCP客户端服务器1.服务器端实现流程2.服务器端代码实现3.客户端实现流程4.客户端代码实现 1.服务器端实现流程 1.创建 event_base 2.创建服务器连接监听器 evc…

服务器运行Vue项目

1.配置nodejs 1.wget获取到nodejs的压缩包 修改成自己需要的版本的下载链接。右键点击&#xff0c;复制下载链接即可。 wget https://nodejs.org/dist/v20.18.1/node-v20.18.1-linux-x64.tar.xz2.解压 tar xf node-v20.18.1-linux-x64.tar.xz3.移动目录 mkdir /usr/local/l…