104. Maximum Depth of Binary Tree

🟢   🔖  树 深度优先搜索 广度优先搜索 二叉树  🔗 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, 104].
• -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 depth = 0;
	let res = 0;
	const traverse = (root) => {
		if (root == null) return;

		depth++;
		res = Math.max(res, depth);
		traverse(root.left);
		traverse(root.right);
		depth--;
	};
	traverse(root);
	return res;
};

相关题目

相关题目

• 110. 平衡二叉树
• 111. 二叉树的最小深度
• 559. N 叉树的最大深度
• 1376. 通知所有员工所需的时间
• 2385. 感染二叉树需要的总时间
• 2458. 移除子树后的二叉树高度

- [110. 平衡二叉树](./0110.md)
- [111. 二叉树的最小深度](./0111.md)
- [559. N 叉树的最大深度](./0559.md)
- [1376. 通知所有员工所需的时间](https://leetcode.com/problems/time-needed-to-inform-all-employees)
- [2385. 感染二叉树需要的总时间](https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected)
- [2458. 移除子树后的二叉树高度](https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries)