Longest Univalue Path


  • 0

    Click here to see the full article post


  • 0
    C
                  4
                 / \
                4   5
               / \   \
              4   4   5
    

    Using one of the solutions, I'm surprised this results in 2 rather than 3 since

              1
             / \
            4   5
           / \   \
          4   4   5
    
    
    also results in 2

  • 0

    @cheesewraps A path is between two nodes, so both trees have an expected answer of 2.


  • 0
    P

    @cheesewraps
    Count number of edges and not number of nodes. 2 is correct answer here.


  • 0

    @awice

    Same idea.

    class Solution {
        int max = 0;
        public int longestUnivaluePath(TreeNode root) {
            max = 0;
            if(root == null) return 0;
            return Math.max(longestUnivaluePathHelper(root.left,root.val) + longestUnivaluePathHelper(root.right,root.val),max);
        }
        
        public int longestUnivaluePathHelper(TreeNode root,int parent_val){
            if(root == null) return 0;
            int left  = longestUnivaluePathHelper(root.left,root.val);
            int right = longestUnivaluePathHelper(root.right,root.val);
            max = Math.max(max,left + right);
            return root.val == parent_val ? 1 + Math.max(left,right) : 0;
        } 
    }
    

  • 0
    1

    @awice
    Could you explain why is answer 2 here ? There is only one path between 4-4( left) and 4-4(right)...max of both is 1
    1
    /
    4 5
    / \
    4 4 5


  • 0
    P

    @12GitTho10
    Question is asking for longest path which has same node value
    combine both left and right
    so the path is
    leftmost 4 -> middle 4 -> right down 4

    as all node values is 4 we have to consider all

    Hope this will help.


  • 0
    1

    @prashantkadam88-gmail.com : Yes Got it :)


  • 0
    S

    Why do we record (arrowLeft + arrowRight) ??why dont we just use line 20 and this will be the answer?


  • 0

    Postorder based on "max path in binary tree":

    class Solution {
    public:
        int max_path = 0;
        int longestUnivaluePath(TreeNode* root) {
            postorder(root);
            return max_path;
        }
        
        int postorder(TreeNode* root) {
            if (root == nullptr) return 0;
            
            int left_length = postorder(root->left);
            int right_length = postorder(root->right);
            
            int lhs = sameas(root->left, root->val) ? left_length : 0;
            int rhs = sameas(root->right, root->val) ? right_length : 0;
            
            max_path = max(max_path, lhs + rhs);
            return max(lhs, rhs) + 1;
        }
        
        bool sameas(TreeNode* node, int value) {
            return node && node->val == value;
        }
    };
    

  • 0
    W

    However, if node.value == node.left.value && node.value == node.right.value,
    you double added root in ans, which is left + 1 + right + 1.


  • 0
    K

    @wqmbisheng which is correct because there are two edges, root to left and root to right.


  • 0
    K

    3
    |
    3
    |
    3
    |
    3 3
    | | \
    2 3 5

    I think this solution would potentially wrong with this types of input, i.e. there's a node whose value == left.val == right.val == its parent.val. Seems like there's no such input, it's not specified in the problem thou.


  • 0
    V

    if (node.left != null && node.left.val == node.val) {
    arrowLeft += left + 1;
    }
    this is assuming that the node has the same value as the nodes in the longest path (in left subtree) which is not always true


  • 0
    R

    Solution described is likely incorrect. Custom inputs of [5,5,5,5,1,5] gives output 4 but i think if i am not mistaken the longest path is 5.


  • 0
    O

    Definition for a binary tree node.

    class TreeNode(object):

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

    class Solution(object):
    def longestUnivaluePath(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    res = [0]
    def front_digui(root,res):
    """利用递归实现树的先序遍历"""
    if root == None:
    return 0
    left= front_digui(root.left,res)
    right= front_digui(root.right,res)
    if root.left:
    left=left+1 if (root.left.val == root.val ) else 0
    if root.right:
    right=right+1 if (root.right.val == root.val ) else 0
    res[0] = max(res[0],left+right)
    return max(left, right)
    front_digui(root,res)
    return res[0]


  • 0
    J

    There appears to be a discrepancy between the task described and the results they desire for this question. Gives the problem description, their test tree of [1,4,5,4,4,null,5] should return 1, but their expected result returns 2 for this tree. Analyzing their expected solution on the test tree [5,5,5,5,1,5] suggested by another user below shows that their solution returns 4, when it should return 2, which makes me think their solution code is incorrectly including some sort of summation (that test tree includes two paths tied for longest length which are both of length 2).


  • 0
    P

    @awice I think some test cases are wrong for this problem. An input like [5,5,5,5,5,4,5] shows Expected answer as 4. But according to the problem description the Correct answer should be 5. Please correct me if I understood the question wrong.


  • 0
    S

    @piku We are counting the edges and not the nodes. The input [5,5,5,5,5,4,5] creates a tree like:

            5
          /   \
         5     5
        / \   / \
       5   5 4   5
    
    

    which has the following longest path with 4 edges:

            5
          /   \
         5     5
        /       \
       5         5
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.