力扣题目汇总分析 利用树形DP解决问题

树里 任意两个节点之间的问题。而不是根节点到叶子节点的问题或者是父节点到子节点的问题。通通一个套路，即利用543的解题思路。

543.二叉树的直径

分析

明确：二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。两个节点之间的最长路径是他们之间的边数。
任意两个节点之间的路径，这个路必然会在一个根节点拐弯(拐弯之后可能继续往下，也可能不继续往下)
所以我们可以遍历每个节点，求出在这个节点拐弯的最长路径，显然，某节点处拐弯的最长路径=左子树的深度+右子树的深度（根节点深度为1）。
利用dfs遍历节点，递归得到子树的深度，原问题与子问题的关系是：子树的深度=max(左子树的深度，右子树的深度)+1。递归终止条件是，当前要遍历的节点是空节点，则返回深度为0。在递归函数中，得到左右子树的深度后，即可以求出当前节点处拐弯的最长路径，定义一个全局变量mm存最长路径，比较当前节点处拐弯的最长路径和全局变量，看看是否要替换。
所以在dfs遍历二叉树的基础上，返回值是当前树的深度，在递归函数体中取得左右子树的深度，算出当前节点处拐弯的最长路径与全局变量mm进行比较。

代码实现

class Solution {int maxDiameter=0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return maxDiameter;}public int dfs(TreeNode root){if (root==null) return 0;//在当前拐弯的最长直径路径=左子树深度+右子树深度int l=dfs(root.left);int r=dfs(root.right);maxDiameter=l+r>maxDiameter?l+r:maxDiameter;return l>r?l+1:r+1;}
}

或

class Solution {int maxDiameter=0;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return maxDiameter;}public int dfs(TreeNode root){if (root==null) return -1;//在当前拐弯的最长直径路径=左子树最长链长度+1+右子树最长链长度+1int l=dfs(root.left)+1;int r=dfs(root.right)+1;maxDiameter=l+r>maxDiameter?l+r:maxDiameter;return l>r?l:r;}
}

687.最长同值路径

分析

这题也是求任意两个节点之间的最长路径，但是加了个条件，路径上的每个节点的值一样。
本来，当前节点处拐弯的最长路径=左子树最长同值路径长度+1+右子树最长同值路径长度+1。
但是，如果左节点的值和当前节点的值不一样，就不考虑左子树（也就相当于让 左子树最长同值路径长度=0），右节点同样操作。

代码实现

class Solution {int mm=0;public int longestUnivaluePath(TreeNode root) {dfs(root);return mm;}public int dfs(TreeNode root){if (root==null) return -1;int l=dfs(root.left)+1;if (root.left!=null && root.left.val!=root.val){l=0;}int r=dfs(root.right)+1;if (root.right!=null && root.right.val!=root.val){r=0;}mm=l+r>mm?l+r:mm;return l>r?l:r;}
}

124.二叉树中的最大路径和

分析

找一条节点序列，序列里每个节点值之和最大。序列里至少有一个节点，序列的起始节点任意。
问题本质和前面的两个题都一样。只是这次找最大的路径上的节点值之和。
当前节点处拐弯的路径上节点之和的最大值=左子树最大路径之和+右子树最大路径之和+当前节点值。
和找同值路径类似，本题中，如果左子树的最大路径之和带来的是负增益，就不考虑（也就是让 左子树最大路径之和=0）。右子树同样操作。

代码实现

class Solution {int mm=-2147483648;public int maxPathSum(TreeNode root) {dfs(root);return mm;}public int dfs(TreeNode root){if (root==null) return 0;int l=dfs(root.left);l=l>0?l:0;int r=dfs(root.right);r=r>0?r:0;mm=l+r+root.val>mm?l+r+root.val:mm;return l>r?l+root.val:r+root.val;}
}

2246.相邻字符不同的最长路径

分析

这题要求找一条最长路径，这个路径上任意一对相邻节点都没有分配到相同字符（最长相邻不同值路径），与前面有所不同的是，这题针对一般的树，而不是二叉树。

所以我们需要取出当前节点的子节点列表，循环遍历，递归处理每个子节点，递归完一个子节点后，如果这个子节点的值和当前节点的值相同，则不考虑（即不参与更新maxNum，mm的操作，当然也可以把值置为0，但是置为0后参与了后续比较操作，属于多余操作）。

当前节点处拐弯的最长不同值路径=子节点中的最大不同值路径长度+1+子节点中不同值路径长度第二大的值+1。

定义一个变量maxNum，存已经遍历的子节点里最大的不同值路径长度，定义一个变量mm，当前节点处拐弯的最长不同值路径的长度，mm每次与 新遍历子节点的最大的不同值路径长度+maxNum进行比较，看看是否替换。如果不可以替换，说明次大的值还是在已经遍历的节点中出现。（通过这种方式，无需创建一个列表存每个子节点的最大不同值路径长度）

代码实现

class Solution {int mm=0;Map<Integer,List<Integer>> map=new HashMap<>();String ss;public int longestPath(int[] parent, String s) {ss=s;for (int i=0;i<parent.length;i++){List<Integer> l=map.getOrDefault(parent[i],new ArrayList<Integer>());l.add(i);map.put(parent[i],l);}dfs(0);return mm+1;}public int dfs(int i){int maxNum=0;if (!map.containsKey(i)){return 0;}for (int c:map.get(i)){int num = dfs(c)+1;if (ss.charAt(c)!=ss.charAt(i)){mm = maxNum+num>mm?maxNum+num:mm;maxNum = num>maxNum?num:maxNum;}}return maxNum;}
}