前言

如果你之前看过这篇深入理解二叉树的前中后序，那么下面这三道题，应该还是比较OK的

104. 二叉树的最大深度

104. 二叉树的最大深度，leetcode链接

函数签名如下：

public int maxDepth(TreeNode root) {
    };

所谓最大深度，就是根节点到「最远」叶子节点的最长路径上的节点数，比如输入这棵二叉树，算法应该返回 3：

你做这题的思路是什么？显然遍历一遍二叉树，用一个外部变量记录每个节点所在的深度，取最大值就可以得到最大深度，这就是遍历二叉树计算的标准思路。

解法代码如下：

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

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

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

这个解法就是标准的遍历思维，但为什么需要在前序位置增加 depth，在后序位置减小 depth？

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

当然，你也会发现一棵二叉树的最大深度可以通过子树的最大高度推导出来，这就是分解问题计算的标准思路。

解法代码如下：

// 定义：输入根节点，返回这棵二叉树的最大深度
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;
}

543. 二叉树的直径

543. 二叉树的直径，leetcode链接

函数签名如下：

public int diameterOfBinaryTree(TreeNode root) {
    };

所谓二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点，比如下面这棵二叉树：

它的最长直径是 3，即 [4,2,1,3] 或者 [5,2,1,3] 这两条「直径」的长度。

解决这题的关键在于，每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。

现在让我们求整棵树中的最长「直径」，那最直接的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。

最大深度的算法我们刚才实现过了，上述思路就可以写出以下代码：

// 记录最大直径的长度
int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    
    maxDepth(root);
    return maxDiameter;
}
// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
    
    if (root == null) return 0;

    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    // 顺便计算最大直径
    int curDiameter = leftMax + rightMax;
    // 当前节点的直径 和 已知的最大直径作比较
    maxDiameter = Math.max(maxDiameter, curDiameter);

    return Math.max(leftMax, rightMax) + 1;
}

124. 二叉树的最大路径和

124. 二叉树的最大路径和，leetcode链接

函数签名如下：

public int maxPathSum(TreeNode root) {
    

做了前面几题，你应该是有了大致思路，这道题和上面的思路其实是一样的，唯一的区别它是计算节点的值。

注：题目说节点的值有可能是负数，那简单啊，负数就不取该节点嘛，不该节点相当于值为0

// 记录最大直径的长度
int maxSum= Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    
    maxValue(root);
    return maxSum;
}
// 定义：输入一个节点，返回以该节点为跟的最大值。
int maxValue(TreeNode root) {
    
    if (root == null) return 0;
	// 递归计算左右节点的最大值
	// 只有在最大值大于0时，才会选取对应的子节点
    int leftValue = Math.max(maxValue(root.left), 0);
    int rightValue = Math.max(maxValue(root.right), 0);
    // 计算当前节点所有节点的值
    int curAllValue = leftValue + rightValue + root.val;
    // 当前节点所有节点的值 和 已知的最大值作比较
    maxSum = Math.max(maxSum, curAllValue);
	// 返回节点的最大值，就是左右子节点中最大的加上它自己的值
    return Math.max(leftValue, rightValue) + root.val;
}

这里要搞清楚两个概念，

• 当前节点的最大值：是递归函数的返回值，也就是左右子节点中最大的值，加上它本身的值。

• 当前节点所有节点的最大值：是左子节点的值，加上右节点的值，加上它本身的值。

你看，当涉及到所有节点的时候，一般都需要借助全局变量