题目描述：给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

示例1:

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例2:

1
2
输入：root = [1,null,2]
输出：2

题解方法一： 深度优先搜索

题目分析：

  • 如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r) + 1,代码实现如下：
    1
    2
    3
    4
    maxDepth = function(root) {
            if (!root) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }

题解方法二： 广度优先搜索

题目分析：

  • 如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r) + 1,代码实现如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var maxDepth = function (root) {
      if (root === null) {
        return 0;
      }

      const queue = []; // BFS 队列
      queue.push(root); // 第一层 根节点 入队列

      let ans = 0;
      while (queue.length) {
        ans++; // 每遍历一层，深度 +1

        let size = queue.length; // 本层节点的数量

        while (size--) { // 遍历本层所有节点
          const node = queue.shift();  // 本层节点依次出队列
          // 当前节点的左子节点入队列
          if (node.left) {
            queue.push(node.left);
          }
          // 当前节点的由子节点入队列
          if (node.right) {
            queue.push(node.right);
          }
        }
      }

      return ans;
    };

    总结：大功告成✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️

参考链接: