【算法题】二叉树根节点到叶子节点的所有路径和

这题说的是计算从根节点到叶子节点的所有路径和，实际上每一条从根节点到叶子节点都构成了一个数字，累加这些数字即可，这些数字只有在叶子节点才能累加，如下图所示。

    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int sum) {
        if (root == null) // 终止条件
            return 0;
        // 计算当前节点的值
        sum = sum * 10 + root.val;
        // 如果当前节点是叶子节点，说明找到了一条完整路径，
        // 直接返回这条路径的值。
        if (root.left == null && root.right == null)
            return sum;
        // 如果当前节点不是叶子结点，返回左右子节点的路径和
        return dfs(root.left, sum) + dfs(root.right, sum);
    }

public:
    int sumNumbers(TreeNode *root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode *root, int sum) {
        if (root == nullptr) // 终止条件
            return 0;
        // 计算当前节点的值
        sum = sum * 10 + root->val;
        // 如果当前节点是叶子节点，说明找到了一条完整路径，
        // 直接返回这条路径的值。
        if (root->left == nullptr && root->right == nullptr)
            return sum;
        // 如果当前节点不是叶子结点，返回左右子节点的路径和
        return dfs(root->left, sum) + dfs(root->right, sum);
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》