先来看看题目吧 这题的解题思路还是比较巧妙的，就是感觉是那种隔山打牛的招式，下面来分析一波 首先，以一个简单的二叉树作为例子 如果以某个节点作为根节点寻找最长同值路径，图中的（2），这种是我们比较容易想到的，但是还有一种情况就是，如（1），以某个节点作为中间节点来寻找最长同值路径，这两种情况看着联系不到一起，但是一种巧妙地思路就可以将两者互相联系在一起，
思路是就是先求情况（2）那种情形，但是情况(2)是情况（1）的一部分，先上代码吧，太难解释了，递归是自底向上，自左向右
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int ans=0; public int longestUnivaluePath(TreeNode root) { helper(root); return ans; } public int helper(TreeNode root){ if(root==null){ return 0; } int maxLength=0;//以root为起点的最长同值路径 int leftLength=helper(root.left);//以root.left为起点的最长同值路径 int rightLength=helper(root.right);//以root.right为起点的最长同值路径 //不需要更新maxLength,但要更新结果 if(root.left!=null&&root.right!=null&&root.left.val==root.val&&root.right.val==root.val){ ans=Math.max(ans,leftLength+rightLength+2); } if(root.left!=null&&root.left.val==root.val){ maxLength=leftLength+1; } if(root.right!=null&&root.right.val==root.val){ maxLength=Math.max(maxLength,rightLength+1); } //更新结果 ans=Math.max(ans,maxLength); return maxLength; } }上面这张图各子树旁边的而标注的数字代表着maxLength,可以看出递归的方向
