3249. Count the Number of Good Nodes Medium

1/**
2 * [3249] Count the Number of Good Nodes
3 *
4 * There is an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
5 * A node is good if all the <span data-keyword="subtree">subtrees</span> rooted at its children have the same size.
6 * Return the number of good nodes in the given tree.
7 * A subtree of treeName is a tree consisting of a node in treeName and all of its descendants.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]</span>
12 * Output: <span class="example-io">7</span>
13 * Explanation:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2024/05/26/tree1.png" style="width: 360px; height: 158px;" />
15 * All of the nodes of the given tree are good.
16 * </div>
17 * <strong class="example">Example 2:
18 * <div class="example-block">
19 * Input: <span class="example-io">edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]</span>
20 * Output: <span class="example-io">6</span>
21 * Explanation:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-2024-06-03-193552.png" style="width: 360px; height: 303px;" />
23 * There are 6 good nodes in the given tree. They are colored in the image above.
24 * <strong class="example">Example 3:
25 * <div class="example-block">
26 * Input: <span class="example-io">edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]</span>
27 * Output: <span class="example-io">12</span>
28 * Explanation:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rob.jpg" style="width: 450px; height: 277px;" />
30 * All nodes except node 9 are good.
31 * </div>
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	2 <= n <= 10^5
37 * 	edges.length == n - 1
38 * 	edges[i].length == 2
39 * 	0 <= ai, bi < n
40 * 	The input is generated such that edges represents a valid tree.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/count-the-number-of-good-nodes/
46// discuss: https://leetcode.com/problems/count-the-number-of-good-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn count_good_nodes(edges: Vec<Vec<i32>>) -> i32 {
52        0
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_3249() {
64    }
65}
66