129. Sum Root to Leaf Numbers
你得到一個僅包含數字 0 到 9 的二叉樹的根節點。
樹中每條從根到葉子的路徑代表一個數字。
例如，從根到葉子的路徑 1 -> 2 -> 3 代表數字 123。 返回所有從根到葉子的數字的總和。測試用例保證答案將適合32位整數。
葉子節點是沒有子節點的節點。
範例：
輸入：root = [1,2,3] 輸出：25 解釋： 從根到葉子的路徑 1->2 代表數字 12。 從根到葉子的路徑 1->3 代表數字 13。 因此，總和 = 12 + 13 = 25。
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, current_sum):
if not node:
return 0
current_sum = current_sum * 10 + node.val
# If it's a leaf node, return the current sum
if not node.left and not node.right:
return current_sum
# Recursively call for left and right subtrees and return the sum
return dfs(node.left, current_sum) + dfs(node.right, current_sum)
return dfs(root, 0)
16.39MB, 28ms
C++
class Solution {
public:
int sumNumbers(TreeNode* root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode* node, int currentSum) {
if (!node) return 0;
currentSum = currentSum * 10 + node->val;
// If it's a leaf node, return the current sum
if (!node->left && !node->right) {
return currentSum;
}
// Recursively call for left and right subtrees and return the sum
return dfs(node->left, currentSum) + dfs(node->right, currentSum);
}
};
11.03MB, 2ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var sumNumbers = function(root) {
const dfs = (node, currentSum) => {
if (!node) return 0;
currentSum = currentSum * 10 + node.val;
// If it's a leaf node, return the current sum
if (!node.left && !node.right) {
return currentSum;
}
// Recursively call for left and right subtrees and return the sum
return dfs(node.left, currentSum) + dfs(node.right, currentSum);
};
return dfs(root, 0);
};
49.7MB, 56ms
