[250. Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees/)

--- tags: leetcode --- # [250. Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees/) --- # My Solution ## Solution 1 ### The Key Idea for Solving This Coding Question ### C++ Code 1 ```cpp= class Solution { public: int countUnivalSubtrees(TreeNode *root) { int cnt = 0; dfs(nullptr, root, cnt); return cnt; } private: // dfs returns true if root and parent is a univalue subtree. // Otherwise, reutrns false. bool dfs(TreeNode *parent, TreeNode *root, int &cnt) { if (root == nullptr) { // root's parent could be a leaf. return true; } bool isLeft = dfs(root, root->left, cnt); bool isRight = dfs(root, root->right, cnt); if (isLeft && isRight) { ++cnt; if (parent != nullptr) { return parent->val == root->val; } // Because parent is nullptr, root is the root of the // whole tree. return true; } return false; } }; ``` ### C++ Code 2 ```cpp= /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countUnivalSubtrees(TreeNode *root) { cnt = 0; dfs(root, INT_MIN); return cnt; } private: int cnt; // dfs returns true if root and its parent is a univalue subtree. // Otherwise, return false. bool dfs(TreeNode *root, int parentVal) { if (root == nullptr) { return true; } bool isLeftUniValue = dfs(root->left, root->val); bool isRightUniValue = dfs(root->right, root->val); if (isLeftUniValue && isRightUniValue) { ++cnt; return root->val == parentVal; } return false; } }; ``` ### Time Complexity $O(n)$ $n$ is the number of nodes in the binary tree referred by `root`. ### Space Complexity $O(H)$ $H$ is the height of the binary tree referred by `root`. ## Solution 2 ### The Key Idea for Solving This Coding Question ### C++ Code ```cpp= class Solution { public: int countUnivalSubtrees(TreeNode *root) { cnt = 0; dfs(root); return cnt; } private: int cnt; void dfs(TreeNode *root) { if (root == nullptr) { return; } dfs(root->left); dfs(root->right); if (isUnivalue(root)) { ++cnt; } } bool isUnivalue (TreeNode *root) { if (root == nullptr) { return true; } if (root->left == nullptr && root->right == nullptr) { return true; } if (root->left == nullptr) { return root->val == root->right->val && isUnivalue(root->right); } if (root->right == nullptr) { return root->val == root->left->val && isUnivalue(root->left); } return root->val == root->left->val && root->val == root->right->val && isUnivalue(root->left) && isUnivalue(root->right); } }; ``` ### Time Complexity $O(n)$ $n$ is the number of nodes in the binary tree referred by `root`. ### Space Complexity $O(H)$ $H$ is the height of the binary tree referred by `root`. # Miscellane