129. Sum Root to Leaf Numbers
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tính tổng tất cả các số được tạo thành từ các đường đi từ gốc đến lá trong một binary tree, mỗi node chứa một chữ số từ 0 → 9. Mỗi đường đi từ root → lá sẽ tạo thành một số nguyên bằng cách nối các giá trị node lại với nhau theo thứ tự đường đi
Approach
current_number = current_number * 10 + node.val Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function sumNumbers(root: TreeNode | null): number {
16 function dfs(node: TreeNode | null, curr_num: number): number {
17 if (!node) return 0;
18 const new_num = curr_num * 10 + node.val
19 if (!node.left && !node.right) return new_num
20 return dfs(node.left, new_num) + dfs(node.right, new_num)
21 }
22 return dfs(root, 0)
23};dfs nhận vào node hiện tại và số đang tạo thành trên đường đi