給定一個二叉樹庸娱，找到最長的路徑恭取，這個路徑中的每個節(jié)點具有相同值。 這條路徑可以經過也可以不經過根節(jié)點俩垃。
注意：兩個節(jié)點之間的路徑長度由它們之間的邊數(shù)表示。
示例 1:
輸入:
Solution:
有三種不同的情況：
左邊子樹路徑最長汰寓，在左子樹中若相同根節(jié)點不同則置為0口柳，相同加一
右邊子樹路徑最長，在有子樹中若是相同根節(jié)點不同則置為0有滑，相同加一
左右子樹加上根節(jié)點路徑最長跃闹。
/**
* Definition for a binary tree node.
* public class TreeNode {
*? ? int val;
*? ? TreeNode left;
*? ? TreeNode right;
*? ? TreeNode(int x) { val = x; }
* }
*/
class Solution {
? ? private int max = 0;
? ? public int longestUnivaluePath(TreeNode root) {
? ? ? ? path(root,root);
? ? ? ? return max;
? ? }
? ? public int path(TreeNode node,TreeNode root){
? ? ? ? if(root==null||node==null) return 0;
? ? ? ? int left = path(node.left,node);? ? ? ? ?//左邊路徑和
? ? ? ? int right = path(node.right,node);? ? //右邊路徑和
? ? ? ? left = (node.left!=null&&node.left.val==node.val)?left+1:0;
? ? ? ? right = (node.right!=null&&node.right.val==node.val)?right+1:0;
? ? ? ? max = Math.max(left+right,max);? ?//取最大
? ? ? ? return Math.max(left,right);? ? ? ? ? ?//返回左右子樹中的最大值。
? ? }
}
