写在前
本部分题目，非自顶向下：就是从任意节点到任意节点的路径，不需要自顶向下
注意：这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决，BFS较DFS繁琐，这里为了简洁只展现DFS代码
1.二叉树最大路径和（124-难）
题目描述：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
思路：递归实现，递归函数的关键写好递归处理的逻辑，怎么处理当前子树，需要返回什么，设置递归出口。关键是正确定义递归函数。
- 递归函数：计算当前节点为父亲节点提供的贡献（即当前节点到根节点的最大路径）。
- 递归的计算左右子节点的最大贡献值，逻辑：贡献值大于0，才会选取对应的节点最大贡献值
- 更新最大路径和（当前节点值和左右子节点最大贡献值）
特别注意：dfs函数中定义的是一个节点能贡献的最大值（计算该节点到根节点的最大路径），而我们统计结果时更新的二叉树中任意两点的最大路径（可能是多个节点到这个根节点的组合）！
代码实现：
private int ans = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
int left = root.left != null && root.val == root.left.val ? l : 0;
int right = root.right != null && root.val == root.right.val ? r : 0;
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
2.最长同值路径（687-中）
题目描述：给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例：
5
/ \
4 5
/ \ \
1 1 5
返回 2
思路：递归实现，思想与上题基本相似。
- 递归函数：当前节点到根节点的最长同值路径
- 递归左右子树的最长同值路径；逻辑：出现同值，更新路径左右路径，否则为0
- 更新最长同值路径
代码实现：
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int dfs(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ans = sum == root.val ? 1 : 0;
sum -= root.val;
return dfs(root.left, sum) + dfs(root.right, sum) + ans;
}
3.二叉树的直径（543-易）
题目描述：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例：
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路：递归实现，递归实现，思想与上题基本相似，还是区分递归函数和最终结果的区别。
代码实现：
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
注意点
- left,right代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
- 全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN，否则就是0
- 注意两点之间路径为1，因此一个点是不能构成路径的
