Concise Javascript solution using recursion


  • 4
    Y

    This solution is based on understanding the problem definition as follows. The longest Univalue Path falls into ONE of the three possible scenarios:

    • It exists somewhere in the Left subtree

    • It exists somewhere in the Right subtree

    • It exists as a straight path from the Left subtree, through the Root, and to a path in the Right subtree.

    Therefore, I needed to write a helper function called straightUnivaluePath, which takes a node and a uniVal, and returns the length of the longest straight path (meaning there is no branching out along the path) through nodes with the uniVal.

    var straightUnivaluePath = function(node, uniVal) {
        if(!node || node.val !== uniVal) return 0;
        return Math.max(straightUnivaluePath(node.left, uniVal), straightUnivaluePath(node.right, uniVal)) + 1;
    }
    
    var longestUnivaluePath = function(root) {
        if(!root) return 0;
        
        return Math.max(
            longestUnivaluePath(root.left),
            longestUnivaluePath(root.right),
            straightUnivaluePath(root.left, root.val) + straightUnivaluePath(root.right, root.val)
        )
    };
    

  • 1
    S

    I think this is my favorite solution so far. Good job!


  • 0
    F

    Very clear, I upvote


  • 0
    F

    Java version

    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int longestUnivaluePath(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return Math.max(straightUnivaluePath(root.left, root.val) + straightUnivaluePath(root.right, root.val), 
                           Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right)));
        }
        private int straightUnivaluePath(TreeNode node, int Univalue) {
            if (node == null || node.val != Univalue) {
                return 0;
            }
            return Math.max(straightUnivaluePath(node.left, Univalue), straightUnivaluePath(node.right, Univalue)) + 1;
        }
    }
    

Log in to reply
 

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