算法思维训练（七）| 树💭-工具盒子

一、树基础知识 {#一-树基础知识}

1. 树概念 {#1--树概念}

二、树知识扩展 {#二-树知识扩展}

1. 树的知识 {#1--树的知识}

略。

树题目 | 二叉树的深度优先搜索 {#树题目---二叉树的深度优先搜索}

题目一：二叉树剪枝 {#题目一-二叉树剪枝}

题目：一棵二叉树的所有节点的值要么是0要么是1，请剪除该二叉树中所有节点的值全都是0的子树。例如，在剪除图（a）中二叉树中所有节点值都为0的子树之后的结果如图（b）所示。

题目分析 {#题目分析}

参考代码 {#参考代码}

Tips：- {#Tips--}

题目二：序列化和反序列化二叉树 {#题目二-序列化和反序列化二叉树}

题目：请设计一个算法将二叉树序列化成一个字符串，并能将该字符串反序列化出原来二叉树的算法。

题目分析 {#题目分析-}

参考代码 {#参考代码-}

Tips：- {#Tips---}

题目三：从根节点到叶节点的路径数字之和 {#题目三-从根节点到叶节点的路径数字之和}

题目：在一棵二叉树中所有节点都在0～9的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如，图的二叉树有3条从根节点到叶节点的路径，它们分别表示数字395、391和302，这3个数字之和是1088。

题目分析 {#题目分析--}

参考代码 {#参考代码--}

Tips：- {#Tips----}

题目四：向下的路径节点值之和 {#题目四-向下的路径节点值之和}

题目：给定一棵二叉树和一个值sum，求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束。例如，在如图所示中的二叉树中有两条路径的节点值之和等于8，其中，第1条路径从节点5开始经过节点2到达节点1，第2条路径从节点2开始到节点6。

题目分析 {#题目分析---}

参考代码 {#参考代码---}

Tips：- {#Tips-----}

题目五：节点值之和最大的路径 {#题目五-节点值之和最大的路径}

题目：在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。给定非空的一棵二叉树，请求出二叉树所有路径上节点值之和的最大值。例如，在如图所示的二叉树中，从节点15开始经过节点20到达节点7的路径的节点值之和为42，是节点值之和最大的路径。

题目分析 {#题目分析----}

参考代码 {#参考代码----}

Tips：- {#Tips------}

树题目 | 二叉搜索树 {#树题目---二叉搜索树}

题目一：展平二叉搜索树 {#题目一-展平二叉搜索树}

题目：给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。例如，把图（a）中的二叉搜索树按照这个规则展平之后的结果如图（b）所示。

题目分析 {#题目分析-----}

参考代码 {#参考代码-----}

Tips：- {#Tips-------}

题目二：二叉搜索树的下一个节点 {#题目二-二叉搜索树的下一个节点}

题目：给定一棵二叉搜索树和它的一个节点p，请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如，在图8.9的二叉搜索树中，节点8的下一个节点是节点9，节点11的下一个节点是null。

题目分析 {#题目分析------}

参考代码 {#参考代码------}

Tips：- {#Tips--------}

题目三：所有大于或等于节点的值之和 {#题目三-所有大于或等于节点的值之和}

题目：给定一棵二叉搜索树，请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如，输入如图（a）所示的二叉搜索树，由于有两个节点的值大于或等于6（即节点6和节点7），因此值为6节点的值替换成13，其他节点的值的替换过程与此类似，所有节点的值替换之后的结果如图（b）所示。

题目分析 {#题目分析-------}

参考代码 {#参考代码-------}

Tips：- {#Tips---------}

题目四：二叉搜索树迭代器 {#题目四-二叉搜索树迭代器}

题目：请实现二叉搜索树的迭代器BSTIterator，它主要有如下3个函数。

构造函数：输入二叉搜索树的根节点初始化该迭代器。
函数next：返回二叉搜索树中下一个最小的节点的值。
函数hasNext：返回二叉搜索树是否还有下一个节点。

题目分析 {#题目分析--------}

参考代码 {#参考代码--------}

Tips：- {#Tips----------}

题目五：二叉搜索树中两个节点的值之和 {#题目五-二叉搜索树中两个节点的值之和}

题目：给定一棵二叉搜索树和一个值k，请判断该二叉搜索树中是否存在值之和等于k的两个节点。假设二叉搜索树中节点的值均唯一。例如，在如图8.12所示的二叉搜索树中，存在值之和等于12的两个节点（节点5和节点7），但不存在值之和为22的两个节点。

题目分析 {#题目分析---------}

参考代码 {#参考代码---------}

Tips：- {#Tips-----------}

树题目 | TreeSet和TreeMap的应用 {#树题目---TreeSet和TreeMap的应用}

题目一：值和下标之差都在给定的范围内 {#题目一-值和下标之差都在给定的范围内}

题目：给定一个整数数组nums和两个正数k、t，请判断是否存在两个不同的下标i和j满足i和j之差的绝对值不大于给定的k，并且两个数值nums[i]和nums[j]的差的绝对值不大于给定的t。

题目分析 {#题目分析----------}

参考代码 {#参考代码----------}

Tips：- {#Tips------------}

题目二：日程表 {#题目二-日程表}

题目：请实现一个类型MyCalendar用来记录自己的日程安排，该类型用方法book（int start，int end）在日程表中添加一个时间区域为[start，end）的事项（这是一个半开半闭区间）。如[start，end）中之前没有安排其他事项，则成功添加该事项并返回true；否则，不能添加该事项，并返回false。