解题步骤

  1. 新建一个变量，记录最大深度
  2. 遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度的这个变量
  3. 遍历结束后返回最大深度的这个变量

通过深度优先遍历实现

  • 时间复杂度：O (n)

  • 空间复杂度：最坏情况O (n)、最好情况O (logn)

    1. function maxDepth(root) {
    2.   let res = 0;
    4.   const dfs = (n, l) => {
    5.       if (!n) return;
    7.       if (l > res) {
    8.           res = l;
    9.       }
    11.       dfs(n.left, l + 1);
    12.       dfs(n.right, l + 1);
    13.   };
    15.   dfs(root, 1);
    17.   return res;
    18. }

上方代码中主要使用了深度优先遍历，遍历了 n 次，n 为当前节点的数量，所以时间复杂度为 O (n)。这段代码中我没有使用数组、矩阵等变量，但是我们用了递归，函数不断调用自身的函数，形成了调用堆栈，调用堆栈在没有被销毁前都是会占用空间的，所以也属于空间复杂度的计算范围内。

最坏的情况下调用堆栈的嵌套层数等于当前的最大深度，也就是空间复杂度是 O (n)。最好的情况下是 O (logn)，因为同样的节点数可能会存在一直单边的情况（刚好都只有单个子节点的情况），所以也会存在刚好都满足两个节点的情况。