NC13.二叉树的最大深度

TIP

标签： 树、深度优先搜索、广度优先搜索、二叉树

题目描述

求给定二叉树的最大深度。最大深度是指树的根节点到最远叶子节点的最长路径上节点的数量。最大深度是所有叶子节点的深度的最大值。

（注：叶子节点是指没有子节点的节点。）

数据范围：0 ≤ n ≤ 100000，树上每个节点的val满足 |val| ≤ 100 要求：空间复杂度 O(1),时间复杂度 O(n)

示例1：

输入：{1,2}
返回值：2

示例2：

输入：{1,2,3,4,#,#,5}
返回值：3

算法思路：

深度优先搜索

如果我们知道了左子树和右子树的最大深度 l 和 r, 那么该二叉树的最大深度为：

max(l,r) + 1

而左子树和右子树的最大深度又可以以同样的方式进行计算，因此我们可以用 『深度优先搜索』的方法来计算二叉树的最大深度，具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在O（1）时间内计算出当前二叉树的最大深度，递归在访问到空节点退出。

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型
  */
// 如果我们知道了左子树和右子树的最大深度l和t, 那么该二叉树的最大深度为：
// max( L,r ) + 1
function maxDepth( root ) {
  // 关于树的问题，能够想到的很好的方法就是递归
  // 既然是使用递归，递归就是要包含递归终止条件和递归语句
  if (root === null) {
    return 0
  }

  let leftDepLength = maxDepth(root.left);
  let rightDepLength = maxDepth(root.right);

  return Math.max(leftDepLength, rightDepLength) + 1;
}
module.exports = {
  maxDepth : maxDepth
};