1022 从根到叶的二进制数之和

简单 DFS

算法思路

显然使用 DFS 即可解决问题。计算过程可以采用递归。最终时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

代码实现

sum-of-root-to-leaf-binary-numbers.c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int isLeaf(struct TreeNode* node) {
    return node->left == NULL && node->right == NULL;
}

int sum = 0;

void addSum(struct TreeNode* node, int val) {
    if (!isLeaf(node)) {
        if (node->left != NULL) {
            addSum(node->left, val * 2 + node->left->val);
        }
        if (node->right != NULL) {
            addSum(node->right, val * 2 + node->right->val);
        }
    } else {
        sum = sum + val;
    }
}

int sumRootToLeaf(struct TreeNode* root) {
    struct TreeNode* node = root;
    addSum(node, node->val);
    return sum;
}