Java 10 lines short solution. No need to use array for return values.


  • 0
    S

    Use positive number to indicate the subtree is uni-value and use negative number to indicate non-uni-value

    public int countUnivalSubtrees(TreeNode root) {
        return (int)Math.abs(countUnivalSubtreesHelper(root));
    }
    public int countUnivalSubtreesHelper(TreeNode root){
        if(root == null)    return 0;
        int leftCnt = countUnivalSubtreesHelper(root.left);
        int rightCnt = countUnivalSubtreesHelper(root.right);
        boolean isUnivalue = leftCnt >= 0 && rightCnt >= 0 && (leftCnt == 0 || root.val == root.left.val) && (rightCnt == 0 || root.val == root.right.val);
        return isUnivalue ? leftCnt + rightCnt + 1 : (leftCnt >= 0? -leftCnt: leftCnt) + (rightCnt >= 0?-rightCnt:rightCnt);
    }

Log in to reply
 

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