Link to LeetCode Problem

S1: DFS

《产品经理法》递归小技巧 练习。

  1. 定义函数功能，先不用管其具体实现。

    首先我们需要这样一个函数：给定一个二叉树的根节点，返回根节点到各个叶子节点连成的数字的和。假设我们已经有这个函数 F，那问题转化成 F(root)。

    唔...其实问题还要复杂一丢丢，因为我们要到叶子节点才能确定递归路径连成的数字，而要知道最终的数字是什么，必须知道该叶子节点的父节点，以及父节点的父节点，...，一直到根节点的数字都要知道。也就是说，我们需要在开始递归的时候用一个变量来记录走过的节点，那现在问题转化成了 F(root, num)。

  2. 确定大问题和小问题的关系。

    首先，遍历到当前节点的时候，还有一点额外的工作要做，就是把当前节点的值记录到 num 中，这一步可以通过数学计算 num * 10 + root.val 来完成，或者用字符串拼接。

    再来看看 F(root, num) 和 F(root.left, num) 以及 F(root.right, num) 的关系，它们的关系就很单纯啦：

    F(root, num) = F(root.left, num) + F(root.right, num)

  3. 补充递归终止条件

    显然，当遍历到叶子节点的时候我们就可以停止了，然后把遍历中生成的数字 num 返回。另外一种情况是遍历的节点不存在，那就直接返回 0 即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return helper(root, 0);
    }
    int helper(TreeNode* root, int num) {
        if (root == nullptr) return 0;
        num = num * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) return num;
        return helper(root->left, num) + helper(root->right, num);
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root, num = 0) {
    if (!root) return 0;
    num = num * 10 + root.val;
    if (!root.left && !root.right) return num;
    return sumNumbers(root.left, num) + sumNumbers(root.right, num);
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNumbers(self, root, num=0):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        num = num * 10 + root.val
        if not root.left and not root.right: return num
        return self.sumNumbers(root.left, num) + self.sumNumbers(root.right, num)

S2: BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;

        int total = 0;
        queue<TreeNode*> level;
        level.push(root);

        while (!level.empty()) {
            int size = level.size();
            while (size--) {
                TreeNode* node = level.front();
                level.pop();

                if (node->left) {
                    node->left->val += node->val * 10;
                    level.push(node->left);
                }
                if (node->right) {
                    node->right->val += node->val * 10;
                    level.push(node->right);
                }
                if (!node->left && !node->right) {
                    total += node->val;
                }
            }
        }
        return total;
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
    if (!root) return 0;

    const queue = [root];
    let sum = 0;
    while (queue.length) {
        let len = queue.length;

        while (len-- > 0) {
            const node = queue.shift();

            if (node.left) {
                node.left.val += node.val * 10;
                queue.push(node.left);
            }

            if (node.right) {
                node.right.val += node.val * 10;
                queue.push(node.right);
            }

            if (!node.left && !node.right) sum += node.val;
        }
    }
    return sum;
};