Concise DFS solution with no global variables


  • 4
    I
    class Solution {
    public:
        int helper(TreeNode* root, int val)
        {
            if(!root || root->val != val) return 0;
            return 1 + max(helper(root->left,val),helper(root->right,val));
        }
        int longestUnivaluePath(TreeNode* root) {
            if(!root) return 0;
            int sub = max(longestUnivaluePath(root->left),longestUnivaluePath(root->right));
            return max(sub,helper(root->left,root->val) + helper(root->right,root->val));
        }
    };
    

  • 2
    G

    @i9r0k cool! I implemented the same algorithm! Here's my take:

    class Solution {
    public:
        int longestUnivaluePath(TreeNode* root) {
            return joint(root);
        }
        
        int joint(TreeNode* n) {
            if (!n) return 0;
            return max(
                max(joint(n->left), joint(n->right)),
                path(n->left, n->val) + path(n->right, n->val)
            );
        }
        
        int path(TreeNode* n, int k) {
            if (!n || n->val != k) return 0;
            return 1 + max(path(n->left, k), path(n->right, k));
        }
    };
    

  • 2

    I like this idea because it does not have any global vars. Here is the java version:

        public int longestUnivaluePath(TreeNode root) {
            if (root == null) return 0;
            int sub = Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right));
            return Math.max(sub, helper(root.left, root.val) + helper(root.right, root.val));
        }
        
        private int helper(TreeNode node, int val) {
            if (node == null || node.val != val) return 0;
            return 1 + Math.max(helper(node.left, val), helper(node.right, val));
        }
    

  • 0
    R

    Can you tell me the time complexity of the above algorithms


  • 0
    G

    @Ronakgoyal29 it appears to be something resembling O(N^2) worst-case.


  • 0
    R

    @garciat Thanks garciat


  • 0
    F

    @garciat Isn't it O(Nlog(N)) average?


  • 0
    G
    This post is deleted!

  • 0
    G

    @fenghao I updated my answer to worst-case.


  • 0
    A

    @OP why are we adding the result from the helper function from the subtrees? Is it because root can lie in a path that (may or may not) start in left subtree and (may or may not) end in right subtree? Is that considered a valid path?


  • 0

    @anand1604 Yes, you can check the second example in the problem description. The longest path is 4-4-4. The valid path can go up and down.


Log in to reply
 

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