题目描述

给定一个二叉树，树的每个节点都包含一个数字（0-9），这棵树的每条从根到叶的路径都代表一个数字。例如，路径1 -> 2 -> 3表示数字123。

计算从根到叶的所有路径所表示的数字之和。

示例：

    1
   / \
  2   3

这棵树的根到叶的路径分别为1->2和1->3，它们分别表示数字12和13，因此数字之和为12 + 13 = 25。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function sumNumbers($root) {
    return dfs($root, 0);
}

function dfs($node, $currentSum) {
    if ($node === null) {
        return 0;
    }

    // 更新当前路径的数字和
    $currentSum = $currentSum * 10 + $node->val;

    // 到达叶子节点，返回当前路径的和
    if ($node->left === null && $node->right === null) {
        return $currentSum;
    }

    // 递归左右子树，并累加结果
    return dfs($node->left, $currentSum) + dfs($node->right, $currentSum);
}

// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
echo sumNumbers($root);  // 输出 25

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumNumbers(root):
    def dfs(node, current_sum):
        if not node:
            return 0
        
        current_sum = current_sum * 10 + node.val
        
        if not node.left and not node.right:
            return current_sum
        
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    return dfs(root, 0)

# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sumNumbers(root))  # 输出 25

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function sumNumbers(root) {
    function dfs(node, currentSum) {
        if (!node) return 0;
        
        currentSum = currentSum * 10 + node.val;
        
        if (!node.left && !node.right) {
            return currentSum;
        }
        
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
    
    return dfs(root, 0);
}

// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
console.log(sumNumbers(root));  // 输出 25

这些示例展示了如何使用深度优先搜索（DFS）来解决这个问题，通过递归遍历树的每个路径，并在到达叶子节点时累加路径表示的数字。