104. Maximum Depth of Binary Tree(E)

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

Solution:

Version 1:

一棵二叉树的最大深度可以通过子树的最大高度推导出来,这就是分解问题计算答案的思路

只要明确递归函数的定义,这个解法也不难理解,但为什么主要的代码逻辑集中在后序位置?

因为这个思路正确的核心在于,你确实可以通过子树的最大高度推导出原树的高度,所以当然要首先利用递归函数的定义算出左右子树的最大深度,然后推出原树的最大深度,主要逻辑自然放在后序位置。

// 定义:输入根节点,返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	// 利用定义,计算左右子树的最大深度
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	// 整棵树的最大深度等于左右子树的最大深度取最大值,
    // 然后再加上根节点自己
	int res = Math.max(leftMax, rightMax) + 1;

	return res;
}

Version 2:

遍历一遍二叉树,用一个外部变量记录每个节点所在的深度,取最大值就可以得到最大深度,这就是遍历二叉树计算答案的思路

这个解法应该很好理解,但为什么需要在前序位置增加 depth,在后序位置减小 depth

因为前面说了,前序位置是进入一个节点的时候,后序位置是离开一个节点的时候,depth 记录当前递归到的节点深度,你把 traverse 理解成在二叉树上游走的一个指针,所以当然要这样维护。

// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;

// 主函数
int maxDepth(TreeNode root) {
	traverse(root);
	return res;
}

// 二叉树遍历框架
void traverse(TreeNode root) {
	if (root == null) {
		// 到达叶子节点,更新最大深度
		res = Math.max(res, depth);
		return;
	}
	// 前序位置
	depth++;
	traverse(root.left);
	traverse(root.right);
	// 后序位置
	depth--;
}

Last updated

Was this helpful?