Pengjielee's blog

题目

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

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

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

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

返回它的最大深度 3 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

补充

高度：从下往上。从最底层开始计数，计数起点是0；
深度：从上往下。从根节点开始计数，计数起点是0；
层次：与深度类似。计数起点是1；根节点在第1层；

节点的高度 = 节点到叶子节点的最长路径（边数）；
节点的深度 = 根节点到这个节点所经历的边的个数；
节点的层数 = 节点的深度 + 1；
树的高度 = 根节点的高度；

JS实现

1、递归实现

参考1：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) {
    return 0;
  }
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

参考2：

var maxDepth = function (root) {
  if (root === null) {
    return 0;
  }
  if (root.left === null && root.right === null) {
    return 1;
  }
  // Number.MIN_SAFE_INTEGER，JavaScript 中最小的安全的integer型数字 (-(2^53 - 1)).
  let max_depth = Number.MIN_SAFE_INTEGER;
  if (root.left != null) {
    max_depth = Math.max(maxDepth(root.left), max_depth);
  }
  if (root.right != null) {
    max_depth = Math.max(maxDepth(root.right), max_depth);
  }
  return max_depth + 1;
};

2、循环实现

参考1：

var maxDepth = function (root) {
  if (!root) {
    return 0;
  }

  const q = [];
  q.push(root);

  let depth = 0;

  while (q.length) {
    const len = q.length;
    while (len > 0) {
      const node = q.shift();
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
      len--;
    }
    depth++;
  }
  return depth;
};

参考2：

var maxDepth = function (root) {
  if (root === null) {
    return 0;
  }

  const queue = [];
  queue.push(root);

  let max_depth = 0;
  while (queue.length > 0) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const curr = queue.shift();
      if (curr.left != null) {
        queue.push(curr.left);
      }
      if (curr.right != null) {
        queue.push(curr.right);
      }
    }
    max_depth++;
  }

  return max_depth;
};