1448.统计二叉树中好节点的数目

链接：1448.统计二叉树中好节点的数目
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

题解 1 - cpp

• 编辑时间：2023-08-25
• 执行用时：112ms
• 内存消耗：84.3MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), mmap[250][250] = {0};
        pair<int, int> prev = make_pair(-1, -1);
        for (int i = 0; i < n; i++) {
            prev = make_pair(-1, -1);
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    if (prev.first == -1) prev = make_pair(i, j);
                    else {
                        mmap[prev.first][prev.second] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        for (int j = 0; j < m; j++) {
            prev = make_pair(-1, -1);
            for (int i = 0; i < n; i++) {
                if (grid[i][j] == 1) {
                    if (prev.first == -1) prev = make_pair(i, j);
                    else {
                        mmap[prev.first][prev.second] = true;
                        mmap[i][j] = true;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (mmap[i][j]) res += 1;
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-08-25
• 执行用时：204ms
• 内存消耗：34.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        res = 0
        def dfs(node: TreeNode, max: int):
            nonlocal res
            if not node: return
            if node.val >= max:
                max = node.val
                res += 1
            dfs(node.left, max)
            dfs(node.right, max)
        dfs(root, -inf)
        return res

题解 3 - rust

• 编辑时间：2023-08-25
• 执行用时：20ms
• 内存消耗：6.7MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut res = 0;
        fn dfs(res: &mut i32, node: &Option<Rc<RefCell<TreeNode>>>, mut max: i32) {
            if let Some(ref node) = node {
                let node_ref = node.as_ref().borrow();
                if node_ref.val >= max {
                    max = node_ref.val;
                    *res += 1;
                }
                dfs(res, &node_ref.left, max);
                dfs(res, &node_ref.right, max);
            }
        }
        dfs(&mut res, &root, i32::MIN);
        res
    }
}