Java Solution not using global variable, DFS


  • 0
    J

    len: self as the root, equal to its own value, the longest path
    maxLen: self as the root, the longest uni-value path in the sub-tree

    class Solution {
        public int longestUnivaluePath(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Result res = preOrder(root);
            return res.maxLen;
        }
        private Result preOrder(TreeNode root) {
            if (root == null) {
                return new Result(0, 0);
            }
            Result leftResult = preOrder(root.left);
            Result rightResult = preOrder(root.right);
            int leftLen = 0;
            int rightLen = 0;
            if (root.left != null && root.left.val == root.val) {
                leftLen = leftResult.len + 1;
            } 
            if (root.right != null && root.right.val == root.val) {
                rightLen = rightResult.len + 1;
            }
            return new Result(Math.max(leftLen, rightLen), Math.max(leftLen + rightLen, Math.max(leftResult.maxLen, rightResult.maxLen)));
        }
    }
    
    class Result {
        int len;
        int maxLen;
        Result(int len, int maxLen) {
            this.len = len;
            this.maxLen = maxLen;
        }
    }
    

Log in to reply
 

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