Easiest to Understand - Java Accepted Code with Explanation


  • 0
    Y

    Almost every tree questions can have such thought to solve. You just consider the tree as a company, the root node is the biggest boss. Apart from the root node, each node has its boss and its lower staff. As a node, you just need to figure out what comes in from your lower staff and what comes out to your boss. Problem's solved.

    class Solution {
        private int max = 0;
        
        public int longestUnivaluePath(TreeNode root) {
            helper(root);
            return max;
        }
        
        private int helper(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = helper(root.left);  // get from lower staff
            int right = helper(root.right);
            if (left != 0) {  // avoid null pointer exception
                if (root.val != root.left.val) {  // if the child has a different value with "this" node, discard the result
                    left = 0;
                }
            }
            if (right != 0) {
                if (root.val != root.right.val) {
                    right = 0;
                }
            }
            if (left + right > max) max = left + right;  // check if the left child and right child can form a path, left == 0 and right == 0 means they have different values with "this" node
            return Math.max(left, right) + 1;  // return to the upper boss
        }
    }
    

Log in to reply
 

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