javascript 解法, 执行用时: 750 ms, 内存消耗: 129.4 MB, 提交时间: 2024-11-14 09:31:52

/**
 * @param {number[][]} edges
 * @return {number}
 */
var countGoodNodes = function(edges) {
    const n = edges.length + 1;
    const g = Array.from({ length: n }, () => []);
    for (const [x, y] of edges) {
        g[x].push(y);
        g[y].push(x);
    }
    let res = 0;
    const dfs = (node, parent) => {
        let valid = true;
        let treeSize = 0;
        let subTreeSize = 0;
        for (const child of g[node]) {
            if (child !== parent) {
                const size = dfs(child, node);
                if (subTreeSize === 0) {
                    subTreeSize = size;
                } else if (size !== subTreeSize) {
                    valid = false;
                }
                treeSize += size;
            }
        }
        if (valid) {
            res++;
        }
        return treeSize + 1;
    };

    dfs(0, -1);
    return res;
};

rust 解法, 执行用时: 83 ms, 内存消耗: 23.5 MB, 提交时间: 2024-11-14 09:31:36

impl Solution {
    pub fn count_good_nodes(edges: Vec<Vec<i32>>) -> i32 {
        let n = edges.len() + 1;
        let mut g = vec![vec![]; n];
        let mut res = 0;
        for edge in edges {
            let (x, y) = (edge[0] as usize, edge[1] as usize);
            g[x].push(y);
            g[y].push(x);
        }

        fn dfs(node: usize, parent: isize, g: &Vec<Vec<usize>>, res: &mut i32) -> usize {
            let mut valid = true;
            let mut tree_size = 0;
            let mut sub_tree_size = 0;

            for &child in &g[node] {
                if child != parent as usize {
                    let size = dfs(child, node as isize, g, res);
                    if sub_tree_size == 0 {
                        sub_tree_size = size;
                    } else if size != sub_tree_size {
                        valid = false;
                    }
                    tree_size += size;
                }
            }
            if valid {
                *res += 1;
            }
            tree_size + 1
        }

        dfs(0, -1, &g, &mut res);
        res
    }
}

java 解法, 执行用时: 105 ms, 内存消耗: 114.3 MB, 提交时间: 2024-08-12 09:43:33

class Solution {
    public int countGoodNodes(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        dfs(0, -1, g);
        return ans;
    }

    private int ans;

    private int dfs(int x, int fa, List<Integer>[] g) {
        int size = 1;
        int pre = 0;
        boolean ok = true;
        for (int y : g[x]) {
            if (y == fa) {
                continue; // 不能递归到父节点
            }
            int sz = dfs(y, x, g);
            if (pre > 0 && sz != pre) {
                ok = false;
            }
            pre = sz; // 记录上一个儿子子树的大小
            size += sz;
        }
        if (ok) {
            ans++;
        }
        return size;
    }
}

cpp 解法, 执行用时: 830 ms, 内存消耗: 325.1 MB, 提交时间: 2024-08-12 09:43:04

class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int ans = 0;
        auto&& dfs = [&](auto&& dfs, int x, int fa) -> int {
            int size = 1, pre = 0;
            bool ok = true;
            for (int y : g[x]) {
                if (y == fa) {
                    continue; // 不能递归到父节点
                }
                int sz = dfs(dfs, y, x);
                if (pre > 0 && sz != pre) {
                    ok = false;
                }
                pre = sz; // 记录上一个儿子子树的大小
                size += sz;
            }
            ans += ok;
            return size;
        };
        dfs(dfs, 0, -1);
        return ans;
    }
};

golang 解法, 执行用时: 451 ms, 内存消耗: 43.5 MB, 提交时间: 2024-08-12 09:41:21

func countGoodNodes(edges [][]int) (ans int) {
	n := len(edges) + 1
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		size, pre, ok := 1, 0, true
		for _, y := range g[x] {
			if y == fa {
				continue // 不能递归到父节点
			}
			sz := dfs(y, x)
			if pre > 0 && sz != pre {
				ok = false
			}
			pre = sz // 记录上一个儿子子树的大小
			size += sz
		}
		if ok {
			ans++
		}
		return size
	}
	dfs(0, -1)
	return
}

python3 解法, 执行用时: 629 ms, 内存消耗: 73.1 MB, 提交时间: 2024-08-12 09:41:06

class Solution:
    def countGoodNodes(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        ans = 0
        # x 开始节点，fa 父节点
        def dfs(x: int, fa: int) -> int:
            size, pre, ok = 1, 0, True
            for y in g[x]:
                if y == fa:
                    continue  # 不能递归到父节点
                sz = dfs(y, x)
                if 0 < pre != sz:
                    ok = False
                pre = sz  # 记录上一个儿子子树的大小
                size += sz
            nonlocal ans
            ans += ok
            return size
        dfs(0, -1)
        return ans