跳至主要內容

104. 二叉树的最大深度


104. 二叉树的最大深度

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

题目

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

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

Output: 3

Example 2:

Input: root = [1,null,2]

Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 10^4].
  • -100 <= Node.val <= 100

题目大意

要求输出一棵树的最大高度。

解题思路

思路一:递归

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


思路二:回溯

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

代码

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

相关题目

题号标题题解标签难度力扣
110平衡二叉树[✓] 深度优先搜索 二叉树🟢🀄️open in new window 🔗open in new window
111二叉树的最小深度[✓] 深度优先搜索 广度优先搜索 1+🟢🀄️open in new window 🔗open in new window
559N 叉树的最大深度[✓] 深度优先搜索 广度优先搜索🟢🀄️open in new window 🔗open in new window
1376通知所有员工所需的时间 深度优先搜索 广度优先搜索🟠🀄️open in new window 🔗open in new window
2385感染二叉树需要的总时间 深度优先搜索 广度优先搜索 2+🟠🀄️open in new window 🔗open in new window
2458移除子树后的二叉树高度[✓] 深度优先搜索 广度优先搜索 2+🔴🀄️open in new window 🔗open in new window