Concise DFS solution with no global variables


  • 5
    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

    @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

    @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
    This post is deleted!

  • 0

    @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.


  • 0
    C

    I think the time complexity should be O(N^2) right ? If we use global variable then it is O(N)...so it seems worthwhile to just use the global variable version...


Log in to reply
 

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