Day23｜二叉树part09：669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇

2024-03-28 15:36
文章标签 二叉树 数组 总结 搜索 转换 108 二叉 有序 累加 day23 538 669 修剪 part09

本文主要是介绍Day23｜二叉树part09：669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

669. 修剪二叉搜索树

一刷完全没有思路，现在有点思路了，但是还是独立写不出来。

class Solution {public TreeNode delete(TreeNode node, int low, int high){if(node == null){return null;}if(node.val < low){return delete(node.right, low, high);}else if(node.val > high){return delete(node.left, low, high);}node.left = delete(node.left, low, high);node.right = delete(node.right, low, high);return node;}public TreeNode trimBST(TreeNode root, int low, int high) {return delete(root, low, high);}
}
  • 如果node（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

所以，如果当前节点的值小于low，那么它的左子树中的所有节点的值也一定小于low。因此，我们可以放心地舍弃当前节点及其左子树，然后在右子树中递归寻找满足条件的节点。

我们会删除那些值不在给定范围内的节点，但是这个“删除”实际上是在寻找和构建新的二叉搜索树，而不是真正意义上的删除操作

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

class Solution {public void testSortedArrayToBST() {// 创建一个二叉搜索树int[] nums = new int[]{-10,-3,0,5,9};TreeNode root = sortedArrayToBST(nums);System.out.println(root.val);}public TreeNode buildBST(int[] nums, int i, int j){if(i > j){return null;}int middle = (i + j) / 2;TreeNode node = new TreeNode(nums[middle]);node.left = buildBST(nums, i, middle - 1);node.right = buildBST(nums, middle + 1, j);return node;}public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length - 1);}
}
  • 这里记得传入的是0, nums.length - 1，不然会越界；

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

看着很难，没想到这么简单！记住遍历顺序是中序但是右中左，用一个sum维护总和。

class Solution {private int sum = 0;public void traversal(TreeNode node){if(node == null){return;}traversal(node.right);sum += node.val;node.val = sum;traversal(node.left);return;}public TreeNode convertBST(TreeNode root) {traversal(root);return root;}
}
  • 为什么是右根左，因为二叉树左小右大。

如果我们按照右-根-左的顺序遍历并更新节点值，那么当我们访问一个节点时，我们已经访问过所有大于该节点值的节点，并且已经计算了它们的和。因此，我们可以直接使用这个和来更新当前节点的值。

114. 二叉树转化为链表

  • 注意 flatten 函数的签名，返回类型为 void，也就是说题目希望我们在原地把二叉树拉平成链表。
  • 否则可以采用这样的方法：
class Solution {private TreeNode dummy = new TreeNode(-1);private TreeNode p = dummy;public void traversal(TreeNode node){if(node == null){return;}p.right = new TreeNode(node.val);p = p.right;traversal(node.left);traversal(node.right);}public void flatten(TreeNode root) {traversal(root);root = dummy.right;}
}

（但是运行后发现并没有修改root的值，这是因为：

，flatten 方法试图修改 root 的引用，但是在 Java 中，参数传递是按值传递的，这意味着你只是复制了 root 的引用，而不是引用本身。因此，当你修改 root 时，你只是修改了这个复制的引用，而不是原始的 root 引用。

  • 因为只能在树上修改，方法是先把左右子树拉平，再把右子树的平序列接到左子树的平序列下面：
class Solution {public void traversal(TreeNode node){if(node == null){return;}//拉平traversal(node.left);traversal(node.right);//保存当前节点的左子节点和右子节点的引用。TreeNode left = node.left;TreeNode right = node.right;node.left = null;node.right = left;//接上TreeNode p = node;while (p.right != null) {p = p.right;}p.right = right;}public void flatten(TreeNode root) {traversal(root);}
}

二叉树总结篇

求二叉树的属性

  • 二叉树：是否对称(opens new window)
    • 递归：后序，比较的是根节点的左子树与右子树是不是相互翻转
    • 迭代：使用队列/栈将两个节点顺序放入容器中进行比较
  • 二叉树：求最大深度(opens new window)
    • 递归：后序，求根节点最大高度就是最大深度，通过递归函数的返回值做计算树的高度
    • 迭代：层序遍历
  • 二叉树：求最小深度(opens new window)
    • 递归：后序，求根节点最小高度就是最小深度，注意最小深度的定义
    • 迭代：层序遍历
  • 二叉树：求有多少个节点(opens new window)
    • 递归：后序，通过递归函数的返回值计算节点数量
    • 迭代：层序遍历
  • 二叉树：是否平衡(opens new window)
    • 递归：后序，注意后序求高度和前序求深度，递归过程判断高度差
    • 迭代：效率很低，不推荐
  • 二叉树：找所有路径(opens new window)
    • 递归：前序，方便让父节点指向子节点，涉及回溯处理根节点到叶子的所有路径
    • 迭代：一个栈模拟递归，一个栈来存放对应的遍历路径
  • 二叉树：递归中如何隐藏着回溯(opens new window)
    • 详解二叉树：找所有路径 (opens new window)中递归如何隐藏着回溯
  • 二叉树：求左叶子之和(opens new window)
    • 递归：后序，必须三层约束条件，才能判断是否是左叶子。
    • 迭代：直接模拟后序遍历
  • 二叉树：求左下角的值(opens new window)
    • 递归：顺序无所谓，优先左孩子搜索，同时找深度最大的叶子节点。
    • 迭代：层序遍历找最后一行最左边
  • 二叉树：求路径总和(opens new window)
    • 递归：顺序无所谓，递归函数返回值为bool类型是为了搜索一条边，没有返回值是搜索整棵树。
    • 迭代：栈里元素不仅要记录节点指针，还要记录从头结点到该节点的路径数值总和

#二叉树的修改与构造

  • 翻转二叉树(opens new window)
    • 递归：前序，交换左右孩子
    • 迭代：直接模拟前序遍历
  • 构造二叉树(opens new window)
    • 递归：前序，重点在于找分割点，分左右区间构造
    • 迭代：比较复杂，意义不大
  • 构造最大的二叉树(opens new window)
    • 递归：前序，分割点为数组最大值，分左右区间构造
    • 迭代：比较复杂，意义不大
  • 合并两个二叉树(opens new window)
    • 递归：前序，同时操作两个树的节点，注意合并的规则
    • 迭代：使用队列，类似层序遍历

#求二叉搜索树的属性

  • 二叉搜索树中的搜索(opens new window)
    • 递归：二叉搜索树的递归是有方向的
    • 迭代：因为有方向，所以迭代法很简单
  • 是不是二叉搜索树(opens new window)
    • 递归：中序，相当于变成了判断一个序列是不是递增的
    • 迭代：模拟中序，逻辑相同
  • 求二叉搜索树的最小绝对差(opens new window)
    • 递归：中序，双指针操作
    • 迭代：模拟中序，逻辑相同
  • 求二叉搜索树的众数(opens new window)
    • 递归：中序，清空结果集的技巧，遍历一遍便可求众数集合
    • 二叉搜索树转成累加树(opens new window)
    • 递归：中序，双指针操作累加
    • 迭代：模拟中序，逻辑相同

#二叉树公共祖先问题

  • 二叉树的公共祖先问题(opens new window)
    • 递归：后序，回溯，找到左子树出现目标值，右子树节点目标值的节点。
    • 迭代：不适合模拟回溯
  • 二叉搜索树的公共祖先问题(opens new window)
    • 递归：顺序无所谓，如果节点的数值在目标区间就是最近公共祖先
    • 迭代：按序遍历

#二叉搜索树的修改与构造

  • 二叉搜索树中的插入操作(opens new window)
    • 递归：顺序无所谓，通过递归函数返回值添加节点
    • 迭代：按序遍历，需要记录插入父节点，这样才能做插入操作
  • 二叉搜索树中的删除操作(opens new window)
    • 递归：前序，想清楚删除非叶子节点的情况
    • 迭代：有序遍历，较复杂
  • 修剪二叉搜索树(opens new window)
    • 递归：前序，通过递归函数返回值删除节点
    • 迭代：有序遍历，较复杂
  • 构造二叉搜索树(opens new window)
    • 递归：前序，数组中间节点分割
    • 迭代：较复杂，通过三个队列来模拟

这篇关于Day23｜二叉树part09：669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/855997。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
LangChain转换链：让数据处理更精准

LangChain转换链：让数据处理更精准

1. 转换链的概念 在开发AI Agent（智能体）时，我们经常需要对输入数据进行预处理，这样可以更好地利用LLM。LangChain提供了一个强大的工具——转换链（TransformChain），它可以帮我们轻松实现这一任务。 转换链（TransformChain）主要是将 给定的数据 按照某个函数进行转换，再将 转换后的结果 输出给LLM。 所以转换链的核心是：根据业务逻辑编写合适的转换函
阅读更多...
十五.各设计模式总结与对比

十五.各设计模式总结与对比

1.各设计模式总结与对比 1.1.课程目标 1、 简要分析GoF 23种设计模式和设计原则,做整体认知。 2、 剖析Spirng的编程思想，启发思维,为之后深入学习Spring做铺垫。 3、 了解各设计模式之间的关联，解决设计模式混淆的问题。 1.2.内容定位 1、 掌握设计模式的"道" ，而不只是"术" 2、 道可道非常道，滴水石穿非一日之功，做好长期修炼的准备。 3、 不要为了
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
Java注解详细总结

Java注解详细总结

什么是注解？         Java注解是代码中的特殊标记，比如@Override、@Test等，作用是：让其他程序根据注解信息决定怎么执行该程序。         注解不光可以用在方法上，还可以用在类上、变量上、构造器上等位置。 自定义注解  现在我们自定义一个MyTest注解 public @interface MyTest{String aaa();boolean bbb()
阅读更多...
tensorboard-----summary用法总结

tensorboard-----summary用法总结

Tensorflow学习笔记——Summary用法         最近在研究tensorflow自带的例程speech_command,顺便学习tensorflow的一些基本用法。 其中tensorboard 作为一款可视化神器，可以说是学习tensorflow时模型训练以及参数可视化的法宝。 而在训练过程中，主要用到了tf.summary()的各类方法，能够保存训练过程以及参数分布图并在
阅读更多...
剑指offer（C++）--数组中只出现一次的数字

剑指offer（C++）--数组中只出现一次的数字

题目 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 class Solution {public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {int len = data.size();if(len<2)return;int one = 0;for(int i
阅读更多...
剑指offer（C++）--平衡二叉树

剑指offer（C++）--平衡二叉树

题目 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 class Solution {public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot==NULL)return true;int left_depth = getdepth(pRoot->left);int right_depth = getdepth(pRoot->rig
阅读更多...
工程文档CAD转换必备！在 Java 中将 DWG 转换为 JPG

工程文档CAD转换必备！在 Java 中将 DWG 转换为 JPG

Aspose.CAD 是一个独立的类库，以加强Java应用程序处理和渲染CAD图纸，而不需要AutoCAD或任何其他渲染工作流程。该CAD类库允许将DWG, DWT, DWF, DWFX, IFC, PLT, DGN, OBJ, STL, IGES, CFF2文件、布局和图层高质量地转换为PDF和光栅图像格式。 Aspose API支持流行文件格式处理，并允许将各类文档导出或转换为固定布局文件格
阅读更多...
二叉树三种遍历方式及其实现

二叉树三种遍历方式及其实现

一、基本概念 每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。 性质： 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 3、对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。 满二叉树：所有终端都在同一层次，且非终端结点的度数为2。 在满二叉树中若其深度为h，则其所包含
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2