999.可以被一步捕获的棋子数

链接：999.可以被一步捕获的棋子数
难度：Easy
标签：数组、矩阵、模拟
简介：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。返回这些数字之和。

题解 1 - python

• 编辑时间：2024-12-06
• 内存消耗：17.23MB
• 编程语言：python
• 解法介绍：遍历。

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        CNT = 8
        x = y = 0
        for i in range(CNT):
            for j in range(CNT):
                if board[i][j] == 'R':
                    x = i
                    y = j
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        res = 0
        for dir in dirs:
            cnt = 1
            while True:
                nx = x + dir[0] * cnt
                ny = y + dir[1] * cnt
                if 0 <= nx < CNT and 0 <= ny < CNT:
                    if board[nx][ny] == '.':
                        cnt += 1
                        continue
                    else:
                        if board[nx][ny] == 'p':
                            res += 1
                break
        return res

题解 2 - cpp

• 编辑时间：2022-05-30
• 执行用时：4ms
• 内存消耗：16.1MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    int sumRootToLeaf(TreeNode* root) {
        int ans = 0;
        dfs(root, ans, 0);
        return ans;
    }
    void dfs(TreeNode* node, int& ans, int val) {
        val = val << 1 | node->val;
        if (node->left == nullptr && node->right == nullptr) {
            ans += val;
            return;
        }
        if (node->left) dfs(node->left, ans, val);
        if (node->right) dfs(node->right, ans, val);
    }
};

题解 3 - cpp

• 编辑时间：2022-03-26
• 内存消耗：16.3MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    int sumRootToLeaf(TreeNode *root) {
        int ans = 0;
        dfs(root, ans, 0);
        return ans;
    }
    void dfs(TreeNode *node, int &ans, int num) {
        if (!node) return;
        num = num << 1 | node->val;
        if (!node->left && !node->right) {
            ans += num;
            return;
        }
        dfs(node->left, ans, num);
        dfs(node->right, ans, num);
    }
};