是lintcode上的一道题,核心算法是深度优先搜索
题干描述:
给定一颗二叉树,找到路径中每个节点具有相同值的最长路径的长度。 此路径可能会也可能不会通过根节点。
提示:
-
两个节点之间的路径长度由它们之间的边数表示。
-
给定的二叉树不超过10000个节点。 树的高度不超过1000。
然后我是发现 @Bo0lean 大佬的题解,他的算法我看得朦朦胧胧不算太懂,想问问有没有人可以帮我详细解释一下,或者有更好的算法也可以提出(最好解释一下,萌新太笨了)
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root:
* @return: the length of the longest path where each node in the path has the same value
*/
int res = 0;
public int longestUnivaluePath(TreeNode root) {
// Write your code here
if(root == null) {
return 0;
}
help(root);
return res;
}
public void help(TreeNode root) {
if(root == null) {
return;
}
int temp = count(root.left, root.val) + count(root.right, root.val);
res = Math.max(res, temp);
help(root.left);
help(root.right);
}
public int count(TreeNode root, int val) {
if(root == null || root.val != val) {
return 0;
}
int left = count(root.left, val) + 1;
int right = count(root.right, val) + 1;
return Math.max(left, right);
}
}