Created
November 29, 2017 01:54
-
-
Save si-yao/66e1836e42ad5d15a7cb97b2341f4dc7 to your computer and use it in GitHub Desktop.
longestUnivaluePath.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package leetcode.longestUnivaluePath; | |
import ds.*; | |
/** | |
* Created by siyao on 9/30/17. | |
* https://leetcode.com/contest/leetcode-weekly-contest-52/problems/longest-univalue-path/ | |
* Solution: | |
* This does not sound like an easy level question. | |
* It is not easy to come up with the correct induction or sub-problem. | |
* So the sub-problm should be, rooting at each node, find the following: | |
* 1. the single side uni-value path starting at the root. | |
* 2. the answer of the question of the sub-tree. | |
* info1 is critical for induction. | |
* | |
* T(n) = 2 * T(n/2) + O(1) = O(n). | |
* | |
* Thinking: | |
* I did not come up with the induction quickly. Think more about it. | |
* | |
*/ | |
class Solution { | |
public int longestUnivaluePath(TreeNode root) { | |
return recur(root)[1]; | |
} | |
// [0] is single side path, [1] is sub-max | |
private int[] recur(TreeNode root) { | |
if (root == null) { | |
return new int[]{0, 0}; | |
} | |
int[] l = recur(root.left); | |
int[] r = recur(root.right); | |
int bothSide = 0; | |
int singleSide = 0; | |
int v = root.val; | |
if (root.left != null && v == root.left.val) { | |
bothSide += 1 + l[0]; | |
singleSide = l[0] + 1; | |
} | |
if (root.right != null && v == root.right.val) { | |
bothSide += 1 + r[0]; | |
singleSide = Math.max(singleSide, r[0] + 1); | |
} | |
bothSide = Math.max(Math.max(bothSide, l[1]), r[1]); | |
return new int[]{singleSide, bothSide}; | |
} | |
} | |
/* | |
687. Longest Univalue Path My SubmissionsBack to Contest | |
User Accepted: 309 | |
User Tried: 545 | |
Total Accepted: 310 | |
Total Submissions: 1089 | |
Difficulty: Easy | |
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. | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment