描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
1
2
3
4
5
2
3
4
5
返回它的最大深度 3 。
题目链接：二叉树的最大深度open in new window
解法
因为 JS 没有二叉树的数据结构，所以新建了一个 TreeNode 的 Class，发现用 TS 写真香...
//Definition for a binary tree node.
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
递归
function maxDepth(root: TreeNode | null): number {
if (root === null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
1
2
3
4
2
3
4
复杂度分析
假设树上一共 n 个节点。
- 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
- 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。
总结
学到了两个操作符：
,逗号操作符 对它的每个操作数求值（从左到右），并返回最后一个操作数的值。!! 表示一定有值 或者 表示 当前值不为 null 和 undefined
可以结合 VScode 的 Code Runner 插件 配置 TS，进行代码调试，两种方式（Node or Deno）可选：