树的题目 | 彩潭有鲤的札记

type

status

date

slug

summary

二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

二叉树的最小深度

题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例：

路径总和

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

示例：

路径总和II

题目：给你二叉树的根节点 root和一个表示目标和的整数 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

示例：

路径总和III

题目：给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例：

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

题目：

给你一个二叉树的根节点root，树中每个节点都存放有一个0到9之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

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

示例：

二叉树中的最大路径和

题目：路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次。该路径 至少包含一个 节点，且不一定经过根节点。路径和是路径中各节点值的总和。给一个二叉树的根节点root ，返回其最大路径和 。

示例：

二叉树的直径

题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

二叉树的右视图

题目：给定一个二叉树的 根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

示例：

相同的树

题目：给两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：

另一棵树的子树

题目：给两棵二叉树root和subRoot 。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true ；否则，返回 false 。二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。

示例：

二叉树展开为链表

题目：

给二叉树的根结点 root ，将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中right子指针指向链表中下一个结点，而左子指针始终为null 。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例：

填充每个节点的下一个右侧节点指针

题目：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。初始状态下，所有next指针都被设置为NULL。

示例：

填充每个节点的下一个右侧节点指针 II

题目：给定一个二叉树：

示例：

二叉树最大宽度

题目：给一棵二叉树的根节点 root ，返回树的 最大宽度 。树的 最大宽度 是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

示例：

求出每一层的宽度，然后求出最大值。求每一层的宽度时，因为两端点间的节点也需要计入宽度，因此可以对节点进行编号。一个编号为的左子节点的编号记为，右子节点的编号记为，计算每层宽度时，用每层节点的最大编号减去最小编号再加1即为宽度。

遍历节点时，可以用广度优先搜索来遍历每一层的节点，并求出最大值。

合并二叉树

题目：

给你两棵二叉树： root1 和 root2 。想象一下，当将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。合并过程必须从两个树的根节点开始。

示例：

序列化二叉树

实现两个函数，分别用来序列化和反序列化二叉树。需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

二叉树的完全性检验

题目：给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

示例：

完全二叉数每一层都是满的，有且只有最后一层的靠右为空根据上面的特性：遍历二叉树的每一层，当遇到空结点之后在遇到不为空结点的结点，说明不为完全二叉树，反之则为完全二叉树