Can someone help? Wrong answer at [5,5,5,5,5,null,5]


  • 0
    L

    Use recursion to find unival subtree count in left child and right child. There are several scenarios:

    1. return 0 if the root is null;
    2. return 1 if it's leaf node;
    3. If one child is null, check whether root's value == child's value
    4. Both children are valid, so if root's value == children's value, return 1+count in left child+count in right child.

    It passed 191/197 test cases, but got wrong answer at [5,5,5,5,5,null,5], it returns 1. I checked manually, it should return 6, not sure why I got wrong answer.

    public int countUnivalSubtrees(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        else if(root.left == null) return root.val == root.right.val?1:0 + countUnivalSubtrees(root.right);
        else if(root.right == null) return root.val == root.left.val?1:0 + countUnivalSubtrees(root.left);
        return (root.val == root.left.val && root.val == root.right.val)?1:0 + countUnivalSubtrees(root.left)+ countUnivalSubtrees(root.right);
    }

  • 0
    S

    My guess is, shouldn't it be like (just pick one line)
    else if(root.left==null) return (root.val == root.right.val? 1: 0)+countUnivalSubtrees(root,right);
    You need a bracket here.
    But even it passes this test case, it will not pass the case like
    2-2-1 where the first 2 has only left child 2 and the second 2 has only left child 1.
    I maybe wrong, you can check that.


Log in to reply
 

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