leetcode-二叉树的最大深度

0728 - 104 - 二叉树的最大深度

二 题目

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

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

/**
 * 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) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

• 递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
/**
 * 思考，方法两种：
 * 1. 递归
 * 2. 遍历
 */
const maxDepth = (root, depth = 1) => {
  if (!root) {
    return 0;
  }
  let tempDepth = depth;
  if (root.left) {
    tempDepth = Math.max(tempDepth, maxDepth(root.left, depth + 1));
  }
  if (root.right) {
    tempDepth = Math.max(tempDepth, maxDepth(root.right, depth + 1));
  }
  return tempDepth;
};

/*
    3
   / \
  9  20
    /  \
   15   7
*/
const root = {
  val: 3,
  left: { val: 9, left: null, right: null },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
};
console.log(maxDepth(root)); // 3

• 迭代

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
/**
 * 思考，方法两种：
 * 1. 递归
 * 2. 遍历
 */
const maxDepth = (root) => {
  if (!root) {
    return 0;
  }
  let depth = 0;
  let cursor = [root];
  while (cursor.length) {
    const tempRoot = [];
    for (let i = 0; i < cursor.length; i++) {
      const nowRoot = cursor[i];
      if (nowRoot.left) {
        tempRoot.push(nowRoot.left);
      }
      if (nowRoot.right) {
        tempRoot.push(nowRoot.right);
      }
    }
    depth++;
    cursor = tempRoot;
  }
  return depth;
};

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。