129. Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13. Therefore, sum = 12 + 13 =25.
Example 2:
Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: The root-to-leaf path4->9->5represents the number 495. The root-to-leaf path4->9->1represents the number 491. The root-to-leaf path4->0represents the number 40. Therefore, sum = 495 + 491 + 40 =1026.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for a binary tree node. | |
| * public class TreeNode { | |
| * int val; | |
| * TreeNode left; | |
| * TreeNode right; | |
| * TreeNode() {} | |
| * TreeNode(int val) { this.val = val; } | |
| * TreeNode(int val, TreeNode left, TreeNode right) { | |
| * this.val = val; | |
| * this.left = left; | |
| * this.right = right; | |
| * } | |
| * } | |
| */ | |
| class Solution { | |
| public int sumNumbers(TreeNode root) { | |
| if (root == null) { | |
| return 0; | |
| } | |
| return dfs(root, 0); | |
| } | |
| private int dfs(TreeNode node, int prefix) { | |
| if (node == null) { | |
| return 0; | |
| } | |
| prefix = prefix * 10 + node.val; | |
| if (node.left == null && node.right == null) { | |
| return prefix; | |
| } | |
| return dfs(node.left, prefix) + dfs(node.right, prefix); | |
| } | |
| } |
