usehook - 前端码易

INFO

请勿第一时间看答案，先自己思考，思考不出来，再看答案

思考题：二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度：是指从根节点到最远叶子节点的最长路径上的节点数。如下图所示的二叉树，最大深度为 3

原题地址：leetcode 104

解题思路

使用递归来解题，主要只关注两个问题

找到规律：如何拆分相同子问题
找到终止条件

我们假定函数 maxDepth(root) 已经可以计算出以 root 为根节点的二叉树的最大深度，那么，对于左右两个子节点，我们会返回值更大的那一边，所以就有如下关系

code.ts

Math.max(maxDepth(root.left), maxDepth(root.right))

当然，每计算一次，会增加一层，所以最终的结果应该是

code.ts

Math.max(maxDepth(root.left), maxDepth(root.right)) + 1

最后我们来思考终止条件。理论上来说，当我们找到叶子节点时，最大深度为 1，所以我们可以返回 1，但是由于在上面的规律中，我们会将左节点与右节点继续传入，叶子节点的左节点与右节点为空

所以，终止条件为

code.ts

if (!root) return 0

完整代码如下

answers.ts

10class TreeNode {
20  val: number
30  left: TreeNode | null
40  right: TreeNode | null
50  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
60    this.val = (val===undefined ? 0 : val)
70    this.left = (left===undefined ? null : left)
80    this.right = (right===undefined ? null : right)
90 }
10}
11
12export function maxDepth(root: TreeNode | null): number {
13  if (root === null) {
14      return 0
15  }
16  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
17};

最大连续 1 的个数

平衡二叉树判断

专栏首页

到顶

专栏目录