剑指 Offer 55 - I. 二叉树的深度
力扣题目链接[1]
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回它的最大深度 3 。
「提示：」
节点总数 <= 10000
思路：
根据题目要求，要求出二叉树的深度。首先会想到使用DFS或者BFS进行题解。
DFS
使用递归实现DFS。递归里的核心逻辑是：树的深度等于左子树的深度和右子树的深度的最大值加一。递归终止条件是，如果当前节点为null，则当前节点不包含在深度内，返回0。
由此可得以下代码：
代码语言：javascript复制/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0;
return Math.max((maxDepth(root.left)), maxDepth(root.right)) 1;
};
- 时间复杂度 O(n)。
- 空间复杂度 O(n)。
分析：
这里使用了递归来实现DFS。复杂度方面，需要遍历二叉树的所有节点，所以时间复杂度是O(n)，当二叉树退化为链表时，调用栈会占用O(n) 的空间。
BFS
使用队列来实现 BFS。核心逻辑是：每遍历到二叉树的一层，计数器就加一。遍历完二叉树的所有层，得到的计时器的值便是二叉树的深度。
代码语言：javascript复制/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0; // 二叉树为空则返回0
let queue = [root]; // 队列中默认添加根节点，方便循环
let res = 0; // 初始化计数器
while(queue.length) {
const length = queue.length; // 获取当前层节点个数
for (let i = 0; i < length; i ) {
const cur = queue.shift();
if (cur.left) queue.push(cur.left);
if (cur.right) queue.push(cur.right);
}
res ; // 计数器累加
}
return res; // 返回计数器
};
- 时间复杂度 O(n)。
- 空间复杂度 O(n)。
分析：
该解法与普通的 BFS 有两处不同。
第一，弹出队列中的元素前，缓存队列的长度，因为队列的长度就是二叉树每一层的节点数。然后循环长度次数，依次将每一层的节点进行处理。
第二，处理完每一层的节点之后，将计数器进行累加。最终计数器的值便是二叉树的深度。
最后返回计数器的值即可。
复杂度方面，需要遍历二叉树的所有节点，因此时间复杂度是O(n) 。当二叉树平衡时，队列中最多存储n/2个节点，因此空间复杂度是O(n)。
总结
本题分别采用 DFS 和 BFS 进行题解。需要掌握两种遍历的代码逻辑思路，同时需要注意广度遍历解法与普通 BFS 的区别。
参考资料
[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9hgr5i/
