[Java/C++] Clean Code


  • 22
    1. Longest-Univalue-Path of a tree is among those Longest-Univalue-Path-Across at each node;
    2. Longest-Univalue-Path-Across a node is sum of { Longest-Univalue-Path-Start-At each child with same value } + 1
    3. Let an dfs to return Longest-Univalue-Path-Start-At each node, the Longest-Univalue-Path-Across node can be calculated by combine the Longest-Univalue-Path-Start-At of its 2 child; and we can use an global variable res to hold the max value and compare with each intermediate result.

    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; // Longest-Univalue-Path-Start-At - left child
            int r = node.right != null ? dfs(node.right, res) : 0; // Longest-Univalue-Path-Start-At - right child
            int resl = node.left != null && node.left.val == node.val ? l + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go left
            int resr = node.right != null && node.right.val == node.val ? r + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go right
            res[0] = Math.max(res[0], resl + resr); // Longest-Univalue-Path-Across - node
            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


  • -1
    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);	
    }
    

  • 0
    Q

    @alexander I dont understand why define res like int[] res = new int[1];
    Why i cant define the res like int res = 0; And i get the wrong result;


  • 1

    @qianrenliang Because java does not support pass parameter by reference, the compiler actually make an copy for any parameter passed in, all you operation inside that method is actually on that copy, so once method return, the variable pass to the method is not changed.

        void foo(int i) {
            int _i = i; // compiler implicitly make an copy on the input parameter
            ...
        }
    

  • 0
    Q

    @alexander Thank you for your patient answer.


  • 1
    T

    @claytonjwong Your post just made me realize the same thing. They need to be more clear in their directions. I've been so confused as to why my code doesn't work... thanks!


  • 0
    O

    @FF_Ti
    public int helper(TreeNode root, int path) don't see any usage for second parameter "path", I think it can be removed.


  • 0
    J

    @FF_Ti Hi, May I ask is here for every node, we add twice the same node because

    for everynode, the max = left + right

    right = length from child + 1

    left = length from child + 1

    Correct me if I am wrong


Log in to reply
 

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