LongestUnivaluePath [source code]
public class LongestUnivaluePath {
static
/******************************************************************************/
class Solution {
public int longestUnivaluePath(TreeNode root) {
if (root == null)
return 0;
return rootPathNodes (root) - 1;
}
int rootPathNodes (TreeNode root) {
if (root == null)
return 0;
TreeNode cur = root;
int left = rootPathNodes (root.left), right = rootPathNodes (root.right);
int myLeft = longestPathNodes (root.left, root.val), myRight = longestPathNodes (root.right, root.val);
return max (left, right, 1 + myLeft + myRight);
}
int longestPathNodes (TreeNode node, int key) {
if (node == null || node.val != key)
return 0;
return Math.max (longestPathNodes (node.left, key), longestPathNodes (node.right, key)) + 1;
}
int max (int... nums) {
int res = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > res)
res = nums[i];
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
LongestUnivaluePath.Solution tester = new LongestUnivaluePath.Solution();
}
}
题目意思不是很难理解, 但是完全没有思路, 题目本身好像有点难; 当然了, 拿到这种tree的问题, 很多时候第一反应就是我一定要想一个O(N)的解法出来, 不过这题O(N)的解法好像真的是完全没有思路, 这个时候你就要relax! 写一个一般化的代码最起码比一行代码都写不出来要好; 所以, 先开始思考一个劣于O(N)的算法; 毕竟note里面给的提示限定了tree的大小, 也许这个就是告诉你如果复杂度不太好, 做不到linear也无所谓的意思?
之前好像做到过一题tree的题目, 最后确实是做不到O(N)的, 所以还是给自己留一点余地;
recursive tree的问题, 很多时候还是要思考, 返回值是什么, 要找到这个recursive return value, which often involves the root; 这里也是类似的思路; 怎样把你最后desire的这个东西的计算转换到跟每一个subtree的root有关系?
另外一个不要忘记的技巧, 也就是以前总结过的, recursion的问题, 要习惯站在children level这一步去思考, 怎么组合; 这里也是类似的; 在这个组合的过程中, 假设你已经拥有了children的返回值, 你怎么组合得到parent的返回值;
最后因为放弃治疗的这种做法, 在时间限制之内把这题做出来了, 但是速度是很惨不忍睹只有36ms (3%), 所以这题肯定是有O(N)算法的; 顺便, 我实际最后run的时候用的case是[1,4,5,4,4,null,5,4,7,2,4], 虽然最后其实没有需要debug, 直接一次就AC了;
另外可以看到我自己写的这几个函数, 都是count的是node而不是edge, 这个实际上也是为了计算方便, 可以作为一个小的技巧记下来;
我这个算法最后这么慢的原因其实我是知道了, 说白了就是longestPathNodes这个函数重复跑了太多次; 一个办法就是augment TreeNode, 先单独跑一遍longestPathNodes, 对于每一个node的结果都记录在augmentation里面, 然后最后再专门跑一次类似rootPathNodes就行了, 所以最后只要走两个pass就行了; 不过理解这个意思就行了;
editorial
Intuition
We can think of any path (of nodes with the same values) as up to two arrows extending from it's root.
Specifically, the root of a path will be the unique node such that the parent of that node does not appear in the path, and an arrow will be a path where the root only has one child node in the path.
Then, for each node, we want to know what is the longest possible arrow extending left, and the longest possible arrow extending right? We can solve this using recursion.
Algorithm
Let arrow_length(node) be the length of the longest arrow that extends from the node. That will be 1 + arrow_length(node.left) if node.left exists and has the same value as node. Similarly for the node.right case.
While we are computing arrow lengths, each candidate answer will be the sum of the arrows in both directions from that node. We record these candidate answers and return the best one.
class Solution {
int ans;
public int longestUnivaluePath(TreeNode root) {
ans = 0;
arrowLength(root);
return ans;
}
public int arrowLength(TreeNode node) {
if (node == null) return 0;
int left = arrowLength(node.left)
int right = arrowLength(node.right);
int arrowLeft = 0, arrowRight = 0;
if (node.left != null && node.left.val == node.val) {
arrowLeft += left + 1;
}
if (node.right != null && node.right.val == node.val) {
arrowRight += right + 1;
}
ans = Math.max(ans, arrowLeft + arrowRight);
return Math.max(arrowLeft, arrowRight);
}
}
这个算法是在我上面自己提出的优化的基础上进一步进行优化: 事实上, 我们不需要记录每一个node的rootPath的长度, 我们只需要一个最大值; 所以用一个global的变量来记录这个最大值; 至于recursion本身, 还是来计算arrow, 或者说root_path就行了;
另外, 看这个算法的时候不是很有把握, 这些value的边界情况; 这个时候一个比较好的办法就是, bottom up, 也就是从最底层的base case开始, 类似于举例子, 从concrete的数据出发, 来理解这些代码计算的到底是什么东西;
通过这个逐步变大的操作的笔算, 可以理解到, 他这里的recursive返回值实际上直接就是edge的count而不是node的count;
其他地方基本没有什么很复杂的东西了, 这个算法核心难点还是要找到怎么定义recursive 返回值, 可以看到awice大神这里对于各种概念的定义非常的严格和准确;
discussion最优解, 类似的算法:
class Solution {
public int longestUnivaluePath(TreeNode root) {
int[] res = new int[1];
if (root != null) dfs(root, res);
return res[0];
}
private int dfs(TreeNode node, int[] res) {
int l = node.left != null ? dfs(node.left, res) : 0; // Longest-Univalue-Path-Start-At - left child
int r = node.right != null ? dfs(node.right, res) : 0; // Longest-Univalue-Path-Start-At - right child
int resl = node.left != null && node.left.val == node.val ? l + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go left
int resr = node.right != null && node.right.val == node.val ? r + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go right
res[0] = Math.max(res[0], resl + resr); // Longest-Univalue-Path-Across - node
return Math.max(resl, resr);
}
}
用array argument来避免global变量的做法也是老生常谈了;
submission基本没有更好的解法, 只是波动;
Problem Description
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
Note: The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
5
/ \
4 5
/ \ \
1 1 5
Output:
2
Example 2:
Input:
1
/ \
4 5
/ \ \
4 4 5
Output:
2
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
Difficulty:Easy
Total Accepted:14.8K
Total Submissions:43.7K
Contributor:1337c0d3r
Companies
google
Related Topics
treerecursion
Similar Questions
Binary Tree Maximum Path SumCount Univalue SubtreesPath Sum III