Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/250.html
250 Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
5
/ \
1 5
/ \ \
5 5 5
return 4.
3 leaf nodes
1 subtree 5-5 of right
@tag-tree
Algorithm
Check from bottom to top, using post-order traversal
, left and right roots, we still call the function recursively.
For the currently traversed node, if the function is called recursively on the left and right child nodes, and the return is true
.
Then it means that the value of the current node and the value of the left and right subtrees are the same, then there is another tree, so the result is incremented by 1.
Code
Java
-
public class Count_Univalue_Subtrees { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. public class Solution_optimize { int res = 0; public int countUnivalSubtrees(TreeNode root) { isUnival(root, -1); return res; } boolean isUnival(TreeNode root, int val) { if (root == null) { return true; } boolean left = isUnival(root.left, root.val); // return meaning left is, and left-val == root-val boolean right = isUnival(root.right, root.val); if (!left | !right) { return false; } ++res; return root.val == val; } } public class Solution { private int result = 0; public int countUnivalSubtrees(TreeNode root) { if (root == null) { return result; } // check selected sub-root and all its decendants if (isUnival(root, root.val)) { ++result; } countUnivalSubtrees(root.left); countUnivalSubtrees(root.right); return result; } boolean isUnival(TreeNode root, int val) { if (root == null) { return true; } return root.val == val && isUnival(root.left, val) && isUnival(root.right, val); } } }
-
// OJ: https://leetcode.com/problems/count-univalue-subtrees/ // Time: O(N) // Space: O(H) where H is the height of the tree class Solution { private: int cnt = 0; bool postorder(TreeNode *root) { if (!root) return true; bool left = postorder(root->left), right = postorder(root->right); if (left && right && (!root->left || root->val == root->left->val) && (!root->right || root->val == root->right->val)) { ++cnt; return true; } return false; } public: int countUnivalSubtrees(TreeNode* root) { postorder(root); return cnt; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int: def dfs(root): if root is None: return True left, right = dfs(root.left), dfs(root.right) t = True if root.left and root.left.val != root.val: t = False if root.right and root.right.val != root.val: t = False nonlocal ans if left and t and right: ans += 1 return left and t and right ans = 0 dfs(root) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def countUnivalSubtrees(self, root): """ :type root: TreeNode :rtype: int """ self.count = 0 def dfs(root, pv): # pv -> parent value if not root: return True left = dfs(root.left, root.val) right = dfs(root.right, root.val) if left and right: self.count += 1 if root.val == pv: return True return False if root: dfs(root, root.val) return self.count