跳至主要內容

55. 二叉树的深度


55. 二叉树的深度open in new window

🟢   🔖  深度优先搜索 广度优先搜索 二叉树  🔗 力扣open in new window

题目

给定一个二叉树 root ,返回其最大深度。

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

示例 1:

输入:root = [3,9,20,null,null,15,7]

输出:3

示例 2:

输入:root = [1,null,2]

输出:2

提示:

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

注意

本题与 LeetCode 第 104 题 相同。

解题思路

思路一:递归

只需求出根节点的左孩子的最大高度和根节点右孩子的最大高度,取出两者的最大值再加一即为根节点的最大高度。


思路二:回溯

深度优先搜索(DFS)一颗二叉树,在 DFS 中,递归返回的时候,我们需要进行回溯(backtrack)。depth 变量用来记录当前节点的深度,每次进入一个子节点时,depth 增加,每次返回到父节点时,depth 需要减少。

代码

递归
/**
 * @param {TreeNode} root
 * @return {number}
 */
var calculateDepth = function (root) {
	if (root == null) return 0;
	return Math.max(calculateDepth(root.left), calculateDepth(root.right)) + 1;
};