二叉树的每个根节点到叶节点的路径代表一个数字，求所有根节点到叶节点所组成数字的和。

这道题的意思是，给定一棵二叉树，每个根节点到叶节点的路径都代表一个数字，求所有路径数字的和。

具体做法是，用深度优先搜索（DFS）遍历二叉树，每当遍历到一个叶节点时，将当前路径上的数字加入总和中。遍历完整棵树后，总和即为所求。

代码实现如下：

int sumNumbers(TreeNode* root) {
    int sum = ;
    dfs(root, , sum);
    return sum;
}

void dfs(TreeNode* root, int cur, int& sum) {
    if (!root) return;
    cur = cur * 10 + root->val;
    if (!root->left && !root->right) {
        sum += cur;
        return;
    }
    dfs(root->left, cur, sum);
    dfs(root->right, cur, sum);
}

其中，dfs函数的三个参数分别为当前节点、当前路径上的数字、总和。如果当前节点为空，则直接返回；否则将当前节点的值加入当前路径上的数字中，并判断当前节点是否为叶节点，如果是，则将当前路径上的数字加入总和中；否则继续遍历左右子树。

相关问题

c语言中如何遍历并输出给定二叉树中从根节点到每个叶节点的所有可能路径？

在C语言中，遍历并输出给定二叉树中从根节点到每个叶节点的所有可能路径，通常可以采用深度优先搜索（DFS），特别是前序、中序或后序遍历结合回溯的方式。这里以前序遍历为例，因为前序遍历先访问根节点，然后左子树，最后右子树，恰好适合这种路径记录。

假设我们有一个结构体`TreeNode`表示二叉树的节点，包含`value`（值）、`left`（左子节点）和`right`（右子节点）：

typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void printPaths(TreeNode* root) {
    if (root == NULL) return; // 如果根节点为空，直接返回
    stack<TreeNode*> pathStack; // 使用栈存储路径
    pathStack.push(root); // 将根节点压入栈

    while (!pathStack.empty()) {
        TreeNode* curr = pathStack.top();
        pathStack.pop(); // 取出当前节点

        printf("%d", curr->value); // 输出节点值

        if (curr->left == NULL && curr->right == NULL) { // 判断是否为叶子节点
            printf(" -> "); // 如果是，打印路径分隔符
        } else if (curr->right != NULL) {
            pathStack.push(curr->right); // 否则，将右子节点压入栈
        }
        
        if (curr->left != NULL) {
            pathStack.push(curr->left); // 再次检查左子节点
        }
    }
}

这个函数会按照前序遍历的顺序输出所有从根节点到叶子节点的路径。如果需要改变路径输出形式，只需调整`printf`部分即可。

给定一个二叉树，求二叉树从根节点到叶节点路径和最大值

可以使用递归的方法来解决该问题。对于每个节点，我们可以将它的值加上它左右子树中路径和最大的那个值，然后返回给它的父节点。对于叶节点，我们直接返回它的值。

具体实现如下：

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        maxPathSum(root, maxSum);
        return maxSum;
    }
    
    int maxPathSum(TreeNode* root, int& maxSum) {
        if (!root) {
            return 0;
        }
        int leftSum = max(0, maxPathSum(root->left, maxSum));
        int rightSum = max(0, maxPathSum(root->right, maxSum));
        maxSum = max(maxSum, root->val + leftSum + rightSum);
        return root->val + max(leftSum, rightSum);
    }
};

其中，maxPathSum函数用于求二叉树的最大路径和，maxPathSum函数用于递归求解每个节点的路径和，并更新maxSum。当节点为空时，返回0；当节点为叶节点时，返回节点值；否则，分别递归求解左右子树的路径和，并取大于等于0的值，然后将左右子树路径和最大的那个值加上节点值作为当前节点的路径和，更新maxSum，并返回当前节点的路径和。

时间复杂度：O(n)，其中n为二叉树节点个数，每个节点访问一次。

空间复杂度：O(h)，其中h为二叉树高度，递归栈空间最多为h层。