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

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

题解 1 - 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);
    }
};

题解 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);
    }
};