0104. Maximum Depth of Binary Tree
==================================
题目信息
--------
:题号: 0104. 二叉树的最大深度
:难度: Easy
:主题: 二叉树、深度优先搜索、后序递归、广度优先搜索
:原题: `LeetCode 0104 `_
:重点: 从枚举根到叶路径,压缩为深度状态,再把全局最值改写成子树高度返回值
题目重述
--------
给定二叉树根节点 ``root``,返回树的最大深度。深度按照节点数计算:从根到最远叶节点的路径包含多少个节点,
最大深度就是多少。因此单节点树的深度为 ``1``,空树的深度为 ``0``。
树中节点总数在 ``0..10^4`` 范围内,节点值在 ``-100..100`` 范围内。节点值不影响深度,算法只读取树的
结构,不修改节点或指针。
自建示例
--------
* 两侧高度不同:``root = [5,2,8,null,3,null,10,null,4]``,返回 ``4``。最长路径为
``5 -> 2 -> 3 -> 4``;
* 单侧链:``root = [1,null,2,null,3]``,返回 ``3``,不能因为每层只有一个节点而少计;
* 单节点:``root = [7]``,返回 ``1``;
* 空树:``root = []``,返回 ``0``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
void updateMaximumDepth(TreeNode* node, int depth, int& maximumDepth) {
if (!node) {
return;
}
maximumDepth = std::max(maximumDepth, depth);
updateMaximumDepth(node->left, depth + 1, maximumDepth);
updateMaximumDepth(node->right, depth + 1, maximumDepth);
}
int topDownDepth(TreeNode* root) {
int maximumDepth = 0;
updateMaximumDepth(root, 1, maximumDepth);
return maximumDepth;
}
int breadthFirstDepth(TreeNode* root) {
if (!root) {
return 0;
}
std::queue pending;
pending.push(root);
int depth = 0;
while (!pending.empty()) {
const int levelSize = static_cast(pending.size());
++depth;
for (int count = 0; count < levelSize; ++count) {
TreeNode* node = pending.front();
pending.pop();
if (node->left) {
pending.push(node->left);
}
if (node->right) {
pending.push(node->right);
}
}
}
return depth;
}
int subtreeHeight(TreeNode* node) {
if (!node) {
return 0;
}
const int leftHeight = subtreeHeight(node->left);
const int rightHeight = subtreeHeight(node->right);
return 1 + std::max(leftHeight, rightHeight);
}
public:
int maxDepth(TreeNode* root) {
return subtreeHeight(root);
}
};
题解
----
原始路径空间
~~~~~~~~~~~~
最大深度来自某一条根到叶路径,因此最直观的正确方案是枚举所有这类路径:沿当前路径不断进入左右孩子,
到叶节点时统计路径包含的节点数,再保留最大值。每个最远节点必然是叶节点,否则还可以继续走向它的孩子,
得到更长路径;所以检查完所有叶节点不会遗漏答案。
若为每个递归分支维护完整的节点数组,真正用于比较的却只有数组长度。路径中的节点值、访问方向和完整副本
都不会影响最大深度。这道题首先要删除的工作不是某个搜索分支,而是路径表示中无关的内容。
深度计数
~~~~~~~~
从根进入孩子时,路径节点数恰好加一,所以可以只携带整数 ``depth``。``updateMaximumDepth`` 进入根时使用
深度 ``1``,每下降一层传入 ``depth + 1``,并用 ``maximumDepth`` 保存目前见过的最大值。
代码在每个非空节点更新最大值,不必专门判断叶节点。非叶节点的深度不会超过其后代,提前参与比较只可能
暂时更新较小值;遍历到最深节点时仍会得到最终答案。空树第一次调用便返回,初始最大值 ``0`` 保持不变。
完整路径数组由一个深度整数替代,但这个自顶向下方案仍有可变的外部状态:子调用通过引用共同修改
``maximumDepth``。还可以换一个观察方向,让每棵子树直接返回自己的答案。
子树高度
~~~~~~~~
定义 ``height(node)`` 为以 ``node`` 为根的子树最大深度。空指针没有节点,高度为 ``0``;非空节点到最远
叶节点的路径必须先计入当前节点,再进入左右子树中更高的一侧:
.. code-block:: text
height(null) = 0
height(node) = 1 + max(height(node.left), height(node.right))
这不是在根处猜测应走左边还是右边。``subtreeHeight`` 先求出两侧各自能达到的最大长度,再舍弃较短者;
任意根到叶路径的第一步只能落在这两侧之一,因此较大值覆盖当前子树的全部候选。
空指针返回 ``0`` 让叶节点自然得到 ``1 + max(0, 0) = 1``,无需额外叶节点分支。每层调用把子问题结果
加一后返回,原来的全局最大值、当前深度参数和进入节点时的更新操作全部消失。公开入口采用这一后序递归,
因为返回值就是当前子树的完整答案,状态边界最清楚。
后序状态走读
~~~~~~~~~~~~
对 ``[5,2,8,null,3,null,10,null,4]``,结果从叶节点向根汇总:
.. list-table::
:header-rows: 1
* - 节点
- 左子树高度
- 右子树高度
- 返回高度
* - 4
- 0
- 0
- 1
* - 3
- 0
- 1
- 2
* - 2
- 0
- 2
- 3
* - 10
- 0
- 0
- 1
* - 8
- 0
- 1
- 2
* - 5
- 3
- 2
- 4
节点 ``5`` 不需要知道左侧最深路径经过哪些具体节点,只接收高度 ``3``;与右侧高度 ``2`` 比较后加一,
便得到整棵树深度 ``4``。这体现了返回状态对完整路径的压缩。
按层计数
~~~~~~~~
``breadthFirstDepth`` 提供不依赖递归的替代方案。队列每轮开始时保存当前层全部节点,固定 ``levelSize`` 后
弹出这一层并加入下一层孩子;每完成一轮,深度加一。最后一层处理结束后队列为空,轮数恰好等于树的层数。
BFS 与后序递归都访问全部节点,只是保存未完成工作的方式不同。后序法保存一条递归路径,空间取决于树高;
BFS 保存层级前沿,空间取决于最大层宽。宽而浅的树更适合递归空间,极深的树则可以用 BFS 避免调用栈风险。
复杂度分析
~~~~~~~~~~
三种实现都访问每个节点一次,时间为 ``O(n)``。自顶向下与后序递归的调用栈为 ``O(h)``,其中 ``h`` 是
树高;单侧链上最坏为 ``O(n)``。BFS 队列工作空间为 ``O(w)``,其中 ``w`` 是最大层宽。所有方法只返回
一个整数,没有与节点数相关的结果空间。