[Java/C++] Clean Code


  • 19

    Longest-Univalue-Path of a tree is among those Longest-Univalue-Path-Across at each node;
    Longest-Univalue-Path-Across a node is sum of { Longest-Univalue-Path-Start-At each child with same value, + 1}

    Java

    class Solution {
        public int longestUnivaluePath(TreeNode root) {
            int[] res = new int[1];
            if (root != null) dfs(root, res);
            return res[0];
        }
    
        private int dfs(TreeNode node, int[] res) {
            int l = node.left != null ? dfs(node.left, res) : 0;
            int r = node.right != null ? dfs(node.right, res) : 0;
            int resl = node.left != null && node.left.val == node.val ? l + 1 : 0;
            int resr = node.right != null && node.right.val == node.val ? r + 1 : 0;
            res[0] = Math.max(res[0], resl + resr);
            return Math.max(resl, resr);
        }
    }
    

    C++

    class Solution {
    public:
        int longestUnivaluePath(TreeNode* root) {
            int lup = 0;
            if (root) dfs(root, lup);
            return lup;
        }
    
    private:
        int dfs(TreeNode* node, int& lup) {
            int l = node->left ? dfs(node->left, lup) : 0;
            int r = node->right ? dfs(node->right, lup) : 0;
            int resl = node->left && node->left->val == node->val ? l + 1 : 0;
            int resr = node->right && node->right->val == node->val ? r + 1 : 0;
            lup = max(lup, resl + resr);
            return max(resl, resr);
        }
    };
    

    Varables
    l is the length of single direction Longest-Univalue-Path start from left-child,
    r is the length of single direction Longest-Univalue-Path start from right-child,
    resl is the length of single direction Longest-Univalue-Path start from parent go left,
    resr is the length of single direction Longest-Univalue-Path start from parent go right.
    int dfs(node) returns the Longest-Univalue-Path-Start-At that node, and update the result of Longest-Univalue-Path-Across that node through side effect.
    It is really hard to name those variables to reflect these concept.

    Example:

                    ...
                   /   
                  4 (res = resl + resr = 3)
      (resl = 2) / \ (resr= 1)
        (l = 1) 4   4 (r = 0)
               /     
              4
    

    resl is Longest-Univalue-Path-Start-At left node + 1,
    resr is Longest-Univalue-Path-Start-At right node + 1,
    in here the local result of Longest-Univalue-Path-Across at this node is the sum of the 2;


  • 1
    Z

    @alexander Very concise!


  • 1

    @alexander thanks for sharing, I came up with a very similar solution (https://discuss.leetcode.com/topic/105653/c-dfs-with-explanation), but I mis-understood the "path" requirement. For example, I thought the following use case should return 3, since there are 3 connections between these nodes with the same value:

        4
       /
      4
     / \
    4   4
    

    However, the actual expected result from above use case is 2, since the "path" is expected to be a linear path ( i.e. NOT upside-down-Y shaped ). @administrators It would be great for above example to be added as a test case for this problem, since I kept failing test cases which were too large to be displayed as a tree, and I could not quickly find out that my understanding of this problem was incorrect.


  • 0
    N

    @alexander said in [Java/C++] Clean Code:

    res[0] = Math.max(res[0], resl + resr);

    @alexander why is res[0] = Math.max(res[0], resl + resr); required?


  • 0

    @naveentrrko
    resl is Longest-Univalue-Path-Start-At left node,
    resr is Longest-Univalue-Path-Start-At right node,
    in here the local result of Longest-Univalue-Path-Across at this node is the sum of the 2;

                    ...
                   /   
                  4 (res = resl + resr = 3)
      (resl = 2) / \ (resr= 1)
        (l = 1) 4   4 (r = 0)
               /     
              4
    

  • 0
    C

    ''return Math.max(resl, resr);''

    I just wonder why you return the bigger one between the left result and the right result?


  • 0

    @chen4393
    l is the length of single direction Longest-Univalue-Path start from left-child,
    r is the length of single direction Longest-Univalue-Path start from right-child,
    resl is the length of single direction Longest-Univalue-Path start from parent go left,
    resr is the length of single direction Longest-Univalue-Path start from parent go right.
    int dfs(node) returns the Longest-Univalue-Path-Start-At that node, and update the result of Longest-Univalue-Path-Across that node through side effect.
    It is really hard to name those variables to reflect these concept.


  • 0
    M

    @alexander forgive me, i am still not getting , why we should use "'return Math.max(resl, resr);" at all ?
    isn't "lup = max(lup, resl+resr)" sufficient to check at each root ?

    why to return max univaue path start at that node ?


  • 0
    M

    @alexander sorry .. got it..nice solution


  • 0
    F
    class Solution {
        int res = 0;
        public int longestUnivaluePath(TreeNode root) {
            helper(root, 0);
            return res;
        }
        public int helper(TreeNode root, int path) {
            if (root == null) {
                return 0;
            }
            int left = helper(root.left, path);
            int right = helper(root.right, path);
            int sum = 0;
            int cur = 0;
            if (root.left != null && root.val == root.left.val) {
                sum += left + 1;
                cur = Math.max(cur, left + 1);
            }
            if (root.right != null && root.val == root.right.val) {
                sum += right + 1;
                cur = Math.max(cur, right + 1);
            }
            res = Math.max(res, sum);
            return cur;
        }
    }
    

  • 0
    B
    static int lup(struct TreeNode* root, int *withMe) {
    	int lLongest, rLongest, longest, lWithMe, rWithMe;
    	if (!root)
    		return 0;
    	longest = lWithMe = rWithMe = 0;
    	lLongest = lup(root->left, &lWithMe);
    	rLongest = lup(root->right, &rWithMe);
    	if (root->left && root->left->val == root->val)
    		*withMe = longest = lWithMe + 1;
    	if (root->right && root->right->val == root->val) {
    		longest += rWithMe + 1;
    		*withMe = max2(*withMe, rWithMe + 1);
    	}
    	return max3(longest, rLongest, lLongest);
    }
    
    int longestUnivaluePath(struct TreeNode* root) {
    	int withMe;
    	return lup(root, &withMe);	
    }
    

Log in to reply
 

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