Another JavaScript solution


  • 0

    Using postorder traversal and return certain information can give us the idea of how the subtrees look like, in this case, each subtree returns the max length of unival on either side, and based on this information, we can calculate the current max length of unival path including the current node.

    If the current node's value is equal to the subtree, simply plus one, otherwise, reset the count from the subtree.

    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var longestUnivaluePath = function(root) {
        var helper = function(node) {
            if (!node) {
                return 0;
            }
            
            var left = helper(node.left);
            var right = helper(node.right);
            
            if (node.left) {
                left += node.left.val === node.val ? 1 : -left;
            }
            
            if (node.right) {
                right += node.right.val === node.val ? 1 : -right;
            }
            
            max = Math.max(max, left + right);
            
            return Math.max(left, right);
        };
        
        var max = 0;
        helper(root);
        return max;
    };
    

    Time complexity O(n), space complexity O(1)

    alt text


Log in to reply
 

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