一天一大 leet(二叉树的最大深度)难度:简单-Day20200728

前端小书童

发布于 2020-09-24 11:43:58

1900

发布于 2020-09-24 11:43:58

文章被收录于专栏：前端小书童

题目:

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

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

示例:

叶子节点是指没有子节点的节点。

说明:

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

返回它的最大深度 3 。

抛砖引玉

思路

之前类似的二叉树题做过:

二叉树中的最大路径和

之前是其最大节点和，本题求最大节点数

任取树中的一个节点，向节点左右两侧遍历
变量的节点为 null 则递归结束，否则返回左右节点计数中较大的值+1
返回值组成：
- 当前这个节点 -> 1
- 当前节点左右侧节点数较多的一侧数量 left-> maxDepth(root.left) right-> maxDepth(root.right)

/**
 * 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 == null) {
    return 0
  } else {
    let left = maxDepth(root.left)
    let right = maxDepth(root.right)
    return Math.max(left, right) + 1
  }
}

广度优先搜索

按层计算

    3       level = [3]
   / \
  9  20     level = [9,20]
    /  \
   15   7   level = [15,7]

声明 level 存放本层所有节点
循环遍历层节点，移除本层节点同时添加其子节点
记录切换层级的次数及最大深度

var maxDepth = function (root) {
  let _result = 0
  if (root == null) {
    return _result
  }
  let level = [root]
  while (level.length) {
    let len = level.length
    while (len > 0) {
      let node = level.shift()
      if (node.left != null) {
        level.push(node.left)
      }
      if (node.right != null) {
        level.push(node.right)
      }
      len--
    }
    _result++
  }
  return _result
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树