DFS最难也就这样了
之前我们已经已经把DFS的核心思想讲清楚了，也就这么回事儿，也再次向大家宣扬了一种循序渐进的思想，从基本解法向外去击破。
我最近在刷Leetcode的时候，也刷了不少跟二叉树相关的题目，大多的套路都很类似，自上而下，从根节点到叶节点，也遇到一些比较有新意的。那我们今天主要目的是来看看DFS里一些算是比较难的题目，看看有新意的题目它会怎么考察对DFS的理解，看看怎么在我们最初的解题模板上去发散到现在的问题，看看究竟是不是这么回事。
首先来看一道中等的题热热身：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
乍一看，直觉告诉我，二叉树找路径，还想要直径最大，那这个路径肯定在两个叶节点之间，转一大圈。那我们大概要走深度优先搜索来遍历了。
那基本方针就这么确定了，那剩下来的就是思考不一样的地方了。这个最长路径可能不经过根节点，这会是个麻烦的地方，我们要想办法处理一下。还要计算每个路径的长度，记录一个最大值。大概就这两个点，我们再在此基础上详细地细分一下具体步骤：
- 每一步，我们要得到当前节点的左右两个子节点的深度，这只要做两个递归就好了。
- 那当前节点的深度也就是左右节点深度的最大值+1。
- 当前节点的直径也就是左节点深度+右节点深度+1。这样我们在每到一个节点时都会计算经过该节点的最长直径是多少。我们可以用一个全局变量保存到目前为止的最长直径，这样在最后我们就能得到最终的最长直径了。
万事俱备！思路都整理明白之后我们来尝试写出来：
public static int findDiameter(TreeNode root) {
calculateHight(root);
return treeDiameter;
}
private static int calculateHight(TreeNode currentNode) {
if (currentNode == null)
return 0;
int leftTreeHeight = calculateHight(currentNode.left);
int rightTreeHeight = calculateHight(currentNode.right);
// 在当前节点的直径等于左子节点深度+右子节点深度+1
int diameter = leftTreeHeight + rightTreeHeight + 1;
// 更新全局最大直径
treeDiameter = Math.max(treeDiameter, diameter);
// 返回当前节点的最大深度用于父节点计算直径
return Math.max(leftTreeHeight, rightTreeHeight) + 1;
}
还是熟悉的配方！我们每次返回当前节点最大的深度用于父节点去计算深度跟最大直径，层层递进，最终就能计算出最长直径。没想到这题目看起来花里胡哨最后还是在基本的DFS递归中加入针对限制条件的处理就好了！
当我把它解出来的时候贼开心。（毕竟这证明了我吹过的牛是正确的，哈哈）有了这道题的经验我们再刷下一道时就好受多了。它是一个套路类似的题目，只不过这次把求最大直径换成了求最大节点之和：给定一个非空二叉树，返回其最大路径和。
现在我们可算是熟门熟路了，我们可以采用跟上题类似的套路解题，用DFS遍历的逻辑不变，只要把计算深度的代码换成求和的代码就可以了，同时为了求最大值，忽略那些和为负数的路径。
那我们可以直接修改一下逻辑了：
public static int findMaximumPathSum(TreeNode root) {
globalMaximumSum = Integer.MIN_VALUE;
findMaximumPathSumRecursive(root);
return globalMaximumSum;
}
private static int findMaximumPathSumRecursive(TreeNode currentNode) {
if (currentNode == null)
return 0;
int maxPathSumFromLeft = findMaximumPathSumRecursive(currentNode.left);
int maxPathSumFromRight = findMaximumPathSumRecursive(currentNode.right);
// 忽略和为负值的路径
maxPathSumFromLeft = Math.max(maxPathSumFromLeft, 0);
maxPathSumFromRight = Math.max(maxPathSumFromRight, 0);
// 当前节点的和等于左子节点加上右子节点的和加上当前节点的值
int localMaximumSum = maxPathSumFromLeft + maxPathSumFromRight + currentNode.val;
// 更新全局变量
globalMaximumSum = Math.max(globalMaximumSum, localMaximumSum);
// 当前节点最大和等于左子节点跟右子节点的最大值加上当前节点的值
return Math.max(maxPathSumFromLeft, maxPathSumFromRight) + currentNode.val;
}
这两道题时间复杂度跟空间复杂度都在O(N)。是不是很开心？即便Leetcode变着花样套路我们，但我们牢牢抓住核心不松手，就算题目条件再复杂，我们也可以一步一步推理出来。
希望能让大家有所收获，Happy coding~