給定一個(gè)二叉樹(shù)咧栗，找到最長(zhǎng)的路徑，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值圆丹。 這條路徑可以經(jīng)過(guò)也可以不經(jīng)過(guò)根節(jié)點(diǎn)居凶。
注意：兩個(gè)節(jié)點(diǎn)之間的路徑長(zhǎng)度由它們之間的邊數(shù)表示虫给。
示例 1:
輸入:
5
/ \
4 5
/ \ \
1 1 5
輸出:
2
示例 2:
輸入:
1
/ \
4 5
/ \ \
4 4 5
輸出:
2
注意: 給定的二叉樹(shù)不超過(guò)10000個(gè)結(jié)點(diǎn)。 樹(shù)的高度不超過(guò)1000侠碧。
分析：
1.如果不仔細(xì)觀察抹估，很容易陷入到一個(gè)TreeNode誤區(qū)，對(duì)于用java解答的小伙伴弄兜，在IDE中解這道題药蜻，很容導(dǎo)包 import javax.swing.tree.TreeNode;，結(jié)果發(fā)現(xiàn)替饿，這個(gè)TreeNode是個(gè)interface呀语泽，這怎么辦？難道要找它的實(shí)現(xiàn)子類视卢？一臉茫然踱卵。淡定，這個(gè)時(shí)候就需要考驗(yàn)審題能力了据过，在平臺(tái)給出的答案區(qū)上方給出了注釋狀態(tài)的一段代碼惋砂，不知道讀者有沒(méi)有留意到？
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
其實(shí)這個(gè)就是本題需要的TreeNode绳锅，當(dāng)我們?cè)谄脚_(tái)上提交答案的時(shí)候西饵，不需要定義這個(gè)class，平臺(tái)驗(yàn)收答案時(shí)是帶著這個(gè)實(shí)現(xiàn)的鳞芙；而當(dāng)我們?cè)贗DE上進(jìn)行編碼調(diào)試的時(shí)候眷柔，需要把這個(gè)TreeNode代碼拷貝到IDE中，解開(kāi)注釋积蜻。然后闯割，就可以正式開(kāi)始解題了。
2.我們來(lái)分析一下題目的關(guān)鍵點(diǎn)竿拆。
二叉樹(shù)：一個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)宙拉，左和右。
路徑：節(jié)點(diǎn)與節(jié)點(diǎn)之間的連線就是一條路徑
同值路徑：節(jié)點(diǎn)和與子節(jié)點(diǎn)或者父節(jié)點(diǎn)之間的值相同丙笋，那么這就是一條同值路徑谢澈，本題求的就是這個(gè)最大值。
邊數(shù)：可以理解為題目示例中連接節(jié)點(diǎn)的直線御板。
3.這一類問(wèn)題梳庆，需要用遞歸的方法解決画髓。在二叉樹(shù)中纵顾，只能從根節(jié)點(diǎn)向下遞歸調(diào)用串慰，可以通過(guò)root.left和root.right的方法得到兩個(gè)子節(jié)點(diǎn)的TreeNode對(duì)象，由此一層一層遞歸調(diào)用下去，直到最底端的葉節(jié)點(diǎn)钉答。
4.第一個(gè)可能遇到的坑：如果當(dāng)前節(jié)點(diǎn)與左節(jié)點(diǎn)的值不同础芍，那么左邊的同值路徑就會(huì)斷掉，同理数尿，如果和右節(jié)點(diǎn)值不同仑性，右邊的同值路徑就會(huì)斷掉。一旦斷掉右蹦，那么當(dāng)前節(jié)點(diǎn)的同值路徑值就應(yīng)該清零诊杆。
5.第二個(gè)可能遇到的坑：如果當(dāng)前節(jié)點(diǎn)與子節(jié)點(diǎn)的值不同，那么從子節(jié)點(diǎn)連過(guò)來(lái)的同值路徑就斷掉了何陆，而如果當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)的值相同晨汹，需要注意，會(huì)從本節(jié)點(diǎn)向父節(jié)點(diǎn)連一個(gè)新的同值路徑甲献，與從子節(jié)點(diǎn)來(lái)的同值路徑無(wú)關(guān)宰缤，不可累加。本題求解的是多條同值路徑中最長(zhǎng)的那條晃洒。
6.第三個(gè)可能遇到的坑：先看下圖，這是平臺(tái)在驗(yàn)證答案時(shí)給出的測(cè)試用例朦乏。
看圖球及，這個(gè)二叉樹(shù)的最大同值路徑就是由根節(jié)點(diǎn)26組成的路徑，從根節(jié)點(diǎn)開(kāi)始呻疹，能連起來(lái)的吃引，值為26的節(jié)點(diǎn)一共是6個(gè)，它們之間的連線一共是5條刽锤，那么答案就是5嗎镊尺？NONO，平臺(tái)的期望值是4并思，明白了嗎庐氮？這里有一個(gè)隱含條件，同值路徑必須是單向的宋彼，就是用紙筆能一筆畫完的弄砍，不能倒退著連。
根據(jù)這些分析输涕，java解答如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int longestUnivaluePath(TreeNode root) {
if (root == null) {
return 0;
}
int[] longestPath = new int[1];
getUnivaluePathCount(root, longestPath);
return longestPath[0];
}
private int getUnivaluePathCount(TreeNode node, int[] longestPath) {
int left = 0;
if (node.left != null) {
left += getUnivaluePathCount(node.left, longestPath);
if (node.val == node.left.val) {
/* 如果本節(jié)點(diǎn)和左節(jié)點(diǎn)值相同音婶，路徑能繼續(xù)，再累加1 */
left += 1;
} else {
/* 否則莱坎，就說(shuō)明左邊的路徑已經(jīng)斷開(kāi)衣式，本節(jié)點(diǎn)的左方向的單向路徑值清零 */
left = 0;
}
}
int right = 0;
if (node.right != null) {
right += getUnivaluePathCount(node.right, longestPath);
if (node.val == node.right.val) {
/* 如果本節(jié)點(diǎn)和右節(jié)點(diǎn)值相同，路徑能繼續(xù)，再累加1 */
right += 1;
} else {
/* 否則碴卧，就說(shuō)明右邊的路徑已經(jīng)斷開(kāi)弱卡，本節(jié)點(diǎn)的右方向的單向路徑值清零 */
right = 0;
}
}
int currentLongestPath;
if (node.left != null && node.right != null && node.left.val == node.right.val) {
/* 如果左右節(jié)點(diǎn)的值相同，那么可以相加連接起來(lái)螟深。但如果左右相同但和本節(jié)點(diǎn)值不同谐宙，那么left和right的值都是0 */
currentLongestPath = left + right;
} else {
/* 否則，最大的路徑值只能是左右路徑的最大值 */
currentLongestPath = Math.max(left, right);
}
if (currentLongestPath > longestPath[0]) {
/* 最終返回的結(jié)果在這里界弧，每次遞歸都是以當(dāng)前節(jié)點(diǎn)為核心凡蜻，計(jì)算最大路徑值，在多次遞歸當(dāng)中垢箕，僅保留最大的值 */
longestPath[0] = currentLongestPath;
}
/* 遞歸返回的是本節(jié)點(diǎn)與左右兩個(gè)子節(jié)點(diǎn)的同值路徑的最大值划栓，注意，如果本節(jié)點(diǎn)的值與左右節(jié)點(diǎn)的值都不同条获，那么返回的是0 */
return Math.max(left, right);
}
}
最后說(shuō)一下忠荞，本答案中的 int[] longestPath 用的java引用傳遞的特性，這并不是唯一的方法帅掘，還可以定義一個(gè)成員變量 private int longestPath; 來(lái)記錄所有的遞歸過(guò)程最大的同值路徑委煤，那樣會(huì)讓遞歸方法少一個(gè)參數(shù)，在大量的遞歸調(diào)用過(guò)程中速度會(huì)更快修档。希望讀者們能學(xué)到這兩種方法碧绞，在今后的開(kāi)發(fā)中根據(jù)實(shí)際情況合理使用。
