104. 二叉树的最大深度
104. 二叉树的最大深度
🟢 🔖 树
深度优先搜索
广度优先搜索
二叉树
🔗 力扣
LeetCode
题目
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;
};
回溯
var maxDepth = function (root) {
let track = 0;
let res = 0;
const backtrack = (root) => {
if (root == null) return;
track++;
res = Math.max(res, track);
backtrack(root.left);
backtrack(root.right);
track--;
};
backtrack(root);
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
110 | 平衡二叉树 | [✓] | 树 深度优先搜索 二叉树 | |
111 | 二叉树的最小深度 | [✓] | 树 深度优先搜索 广度优先搜索 1+ | |
559 | N 叉树的最大深度 | [✓] | 树 深度优先搜索 广度优先搜索 | |
1376 | 通知所有员工所需的时间 | 树 深度优先搜索 广度优先搜索 | ||
2385 | 感染二叉树需要的总时间 | 树 深度优先搜索 广度优先搜索 2+ | ||
2458 | 移除子树后的二叉树高度 | [✓] | 树 深度优先搜索 广度优先搜索 2+ |