# 描述

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:  叶子节点是指没有子节点的节点。

示例: 给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度  3 。

题目链接:二叉树的最大深度 (opens 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;
  }
}

# 递归

function maxDepth(root: TreeNode | null): number {
  if (root === null) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

复杂度分析

假设树上一共 n 个节点。

  • 时间复杂度:这里遍历了这棵树,渐进时间复杂度为 O(n)。
  • 空间复杂度:这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。

# 总结

学到了两个操作符:

  • , 逗号操作符 对它的每个操作数求值(从左到右),并返回最后一个操作数的值。
  • ! ! 表示一定有值 或者 表示 当前值不为 null 和 undefined

可以结合 VScode 的 Code Runner 插件 配置 TS,进行代码调试,两种方式(Node or Deno)可选:

上次更新: 4/21/2021, 10:23:16 AM