C# - recursive - bottom up, no member count variable


  • 0

    Instead of using a member variable to keep track of count, we can alternately use the return value from our recursive function to signal both the accumulative count and if the unival rule is broken. To get this we use negative count to signal that unival rule is broken.

        public int CountUnivalSubtrees(TreeNode root) 
        {
            if (root == null) return 0;
            return Math.Abs(CountUnival(root));
        }
        
        // return accumulative count of Unival Subtrees, use negative to signal no longer unival
        public int CountUnival(TreeNode node)
        {
            int left = (node.left != null) ? CountUnival(node.left) : 0;
            int right = (node.right != null) ? CountUnival(node.right) : 0;
            
            bool isUni = (left == 0 || (left > 0 && node.left.val == node.val))
                        && (right == 0 || (right > 0 && node.right.val == node.val));
                        
            int count = isUni ? (1 + left + right) : (Math.Abs(left) + Math.Abs(right));
            return isUni ? count : -count;
        }
    

    Just to see I submitted this additional solution which I did not expect to get accepted. Notice that it does a lot of duplicate work but still was Accepted. I would have expected TLE on this solution. Perhaps another test case is needed to reject this solution.

        public int CountUnivalSubtrees(TreeNode root) 
        {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 1;
            int count = 0;
            count += IsUni(root, root.val) ? 1 : 0;
            count += CountUnivalSubtrees(root.left) + CountUnivalSubtrees(root.right);
            return count;
        }
        
        public bool IsUni(TreeNode node, int val)
        {
            if (node == null) return true;
            if (node.val != val) return false;
            return IsUni(node.left, val) && IsUni(node.right, val);
        }
    

Log in to reply
 

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