Maximum Depth of Binary Tree
给你一个按层序存储在数组 tree 中的二叉树。根节点位于索引 0 处，索引 i 处节点的左子节点位于 2*i+1 处，右子节点位于 2*i+2 处，-1 表示空位置，数组末尾可能还有额外的 -1 项。返回这棵树的最大深度：从根节点到叶节点的最长路径上的节点数。
函数
- treeinteger-array
- 按层序表示的二叉树，空位置用 -1 表示
- 返回值integer
- 从根节点到叶节点的最长路径上的节点数
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或满足0 ≤ tree[i] ≤ 1000的值。 tree[0]永远不会是-1，因此这棵树至少有一个节点。- 数组末尾在最后一个节点之后可能还有额外的
-1项。 - 空位置的两个子节点也都是空的，并且深度最多为
14。
示例
- 输入
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- 输出
- 4
- 解释
- 最长路径是
5、8、3、6（索引为0、1、4、9），包含 4 个节点。经过1的路径在 2 个节点后就结束了。
- 输入
- tree = [7, -1, -1]
- 输出
- 1
- 解释
- 这两个
-1条目表示根节点的空子节点位置。根节点本身就是一条包含一个节点的路径，所以深度是1，不是0。
- 输入
- tree = [2, -1, 9, -1, -1, -1, 4]
- 输出
- 3
- 解释
- 根节点
2没有左子节点。它的右子节点9位于索引2，其右子节点是位于索引6的4，这条路径包含 3 个节点。
进阶
如何返回最长根到叶路径上的值以及它的长度？如果有多条路径长度相同，你会返回哪一条？
提示
逐个打开提示，每个都会多透露一点。
想一想根节点。如果你知道它的左子树和右子树的深度，整棵树的深度是多少？
它等于
1加上两个子树深度中较大的那个，空位置的深度为0。每个节点都遵循同样的规则，因此，只要遍历时知道每个节点的深度，就能找到答案。维护一个由节点索引和深度组成的对的栈，初始时将根节点的深度设为 1。弹出一对，记住已见到的最大深度，然后将每个索引为
2*i+1和2*i+2、位于数组范围内且不等于-1的子节点压入栈中，深度加 1。
题解
深度由最长的分支决定，而你必须访问每个节点，才能知道哪条分支最长。因此，你需要进行一次完整遍历，并在访问每个节点时记录它的深度。递归、按层进行的广度优先搜索，以及使用自己的栈进行的深度优先搜索，都可以一次遍历完成这项工作。
对两个子树进行递归
思路
当子节点位置的索引在数组范围内，且其值不为 -1 时，该位置才有效。经过一个节点的最深路径会向下进入更深的子树，因此，索引 i 处的深度为 1 加上 2*i+1 和 2*i+2 处深度中的较大值。空位置的深度为 0，这会结束递归。叶节点的深度为 1 + max(0, 0) = 1，然后这些值会一路向上返回到根节点。
每个节点只会访问一次。调用栈会为当前路径的每一层保存一个栈帧，空间复杂度为 O(h)，这里最多为 14 层。
算法
- 编写
depth(i)：如果i超出数组末尾，或者tree[i]是-1，则返回0。 - 否则返回
1 + max(depth(2*i+1), depth(2*i+2))。 - 返回
depth(0)。
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)广度优先搜索，逐层进行
思路
最大深度就是层数，因此你可以直接数层，而不必沿着路径遍历。队列按层访问节点。每批处理前，先读取队列的大小：这些节点正好属于同一层，因为你在处理这一批时添加的子节点会排在它们后面。每批处理都会让深度加 1。在第一个示例中，各批节点为 [5]、[8, 1]、[3] 和 [6]，所以答案是 4。
队列一次只保存一层节点，空间复杂度为最宽一层的 O(w)。对于深度为 14 的满二叉树，这一层有 8192 个节点，而整棵树共有 16383 个节点。
算法
- 将根索引
0放入队列，并设置depth = 0。 - 当队列不为空时，将
depth加1，并读取队列的大小。 - 取出这么多个索引。对于每个索引，将位于数组内且不为
-1的子索引2*i+1和2*i+2放入队列。 - 队列为空时，返回
depth。
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depth使用显式栈进行深度优先搜索
思路
你需要自己维护一个由节点索引和深度组成的栈，因为没有其他东西会记录节点位于多深处。从 (0, 1) 开始，根节点的深度为 1。每个节点都会入栈一次，并携带通向它的路径长度，因此你弹出的最大深度就是答案。在第一个示例中，6 会以 (9, 4) 的形式入栈。
这个栈大约只保存每一层一个待处理的兄弟节点，占用 O(h) 空间，而且没有可能溢出的调用栈。同一段代码适用于任意深度的基于指针的树。
算法
- 将
(0, 1)压入栈，并设置best = 0。 - 弹出一对
(i, depth)，并将best设置为best和depth中较大的值。 - 对于每个子节点索引
2*i+1和2*i+2，如果它在数组范围内且不等于-1，就将它与depth + 1一起压入栈。 - 重复上述步骤，直到栈为空，然后返回
best。
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
易错点和边界情况
- 把边数当成节点数来计数。
[7, -1, -1]的深度是1，不是0。 - 跳过边界检查。在第一个示例中，索引 9 处的
6的子节点索引是 19 和 20，超出了数组的范围。在读取tree[child]之前，先检查child < n。 - 根据数组长度计算深度。末尾的
-1条目会到达没有节点的层级：[7, -1, -1]的长度是 3，但深度是 1。 - 在批次循环中读取队列的大小。批次期间添加的子节点会改变队列大小，所以要先保存大小。
- 混淆 Lua 和 R 中的偏移量，因为数组从 1 开始。节点索引保持从 0 开始，用于
2*i+1，并读取tree[i + 1]。
常见问题3
二叉树的最大深度的时间复杂度是多少？
每种方法都会访问每个节点一次，因此时间复杂度为 O(n)。深度优先版本会使用 O(h) 的额外空间来保存当前路径，其中 h 是深度。广度优先版本会使用 O(w) 的空间来保存最宽的一层，对于满二叉树来说，这一层大约包含一半的节点。
求二叉树的最大深度时，应该使用 DFS 还是 BFS？
两者的运行时间都是 O(n)。深度优先搜索写起来更短，使用的内存与深度成正比，因此适合宽而浅的树。广度优先搜索直接统计层数，使用的内存与最宽的一层成正比，因此适合深而窄的树。对于最小深度，广度优先搜索更有优势，因为它可以在遇到第一个叶节点时停止。
二叉树的深度和高度有什么区别？
节点的深度是从根节点到该节点的步数；高度是从该节点到最深叶节点的步数。树的最大深度等于根节点的高度。本题按节点计数，因此单个节点的深度为 1；按边计数则会少 1。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def maxDepth(tree):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
预期输出
4