250. Count Univalue Subtrees

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int countUnivalSubtrees(TreeNode* root) { int ans = 0; isUnival(root, INT_MAX, ans); return ans; } private: bool isUnival(TreeNode* root, int val, int& ans) { if (root == nullptr) return true; if (isUnival(root->left, root->val, ans) & isUnival(root->right, root->val, ans)) { ++ans; return root->val == val; } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int countUnivalSubtrees(TreeNode root) { isUnival(root, Integer.MAX_VALUE); return ans; } private int ans = 0; private boolean isUnival(TreeNode root, int val) { if (root == null) return true; if (isUnival(root.left, root.val) & isUnival(root.right, root.val)) { ++ans; return root.val == val; } return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int: ans = 0 def isUnival(root: Optional[TreeNode], val: int) -> bool: nonlocal ans if not root: return True if isUnival(root.left, root.val) & isUnival(root.right, root.val): ans += 1 return root.val == val return False isUnival(root, math.inf) return ans