Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/250.html
Given the root
of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
Example 1:
Input: root = [5,1,5,5,5,null,5] Output: 4
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [5,5,5,5,5,null,5] Output: 6
Constraints:
- The number of the node in the tree will be in the range
[0, 1000]
. -1000 <= Node.val <= 1000
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
-
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); } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans; public int countUnivalSubtrees(TreeNode root) { ans = 0; dfs(root); return ans; } private boolean dfs(TreeNode root) { if (root == null) { return true; } boolean left = dfs(root.left); boolean right = dfs(root.right); boolean t = true; if (root.left != null && root.left.val != root.val) { t = false; } if (root.right != null && root.right.val != root.val) { t = false; } if (left && t && right) { ++ans; } return left && t && right; } }
-
// 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: TreeNode) -> int: count = 0 def is_unival(node): nonlocal count if not node: return True left_unival = is_unival(node.left) right_unival = is_unival(node.right) if left_unival and right_unival: if node.left and node.val != node.left.val: return False if node.right and node.val != node.right.val: return False count += 1 return True return False is_unival(root) return count class Solution: # return 2 values def countUnivalSubtrees(self, root: TreeNode) -> int: def is_unival(node): if not node: return True, 0 left_unival, left_count = is_unival(node.left) right_unival, right_count = is_unival(node.right) if left_unival and right_unival: if node.left and node.val != node.left.val: return False, 0 if node.right and node.val != node.right.val: return False, 0 return True, left_count + right_count + 1 return False, 0 _, count = is_unival(root) return count
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func countUnivalSubtrees(root *TreeNode) int { ans := 0 var dfs func(root *TreeNode) bool dfs = func(root *TreeNode) bool { if root == nil { return true } left, right := dfs(root.Left), dfs(root.Right) t := true if root.Left != nil && root.Left.Val != root.Val { t = false } if root.Right != nil && root.Right.Val != root.Val { t = false } if left && t && right { ans++ } return left && t && right } dfs(root) return ans }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var countUnivalSubtrees = function (root) { let ans = 0; let dfs = function (root) { if (!root) { return true; } const left = dfs(root.left), right = dfs(root.right); let t = true; if (root.left && root.left.val != root.val) { t = false; } if (root.right && root.right.val != root.val) { t = false; } if (left && t && right) { ++ans; } return left && t && right; }; dfs(root); return ans; };
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function countUnivalSubtrees(root: TreeNode | null): number { let ans: number = 0; const dfs = (root: TreeNode | null): boolean => { if (root == null) { return true; } const l: boolean = dfs(root.left); const r: boolean = dfs(root.right); if (!l || !r) { return false; } if (root.left != null && root.left.val != root.val) { return false; } if (root.right != null && root.right.val != root.val) { return false; } ++ans; return true; }; dfs(root); return ans; }