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->2
represents the number12
. The root-to-leaf path1->3
represents 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->5
represents the number 495. The root-to-leaf path4->9->1
represents the number 491. The root-to-leaf path4->0
represents the number 40. Therefore, sum = 495 + 491 + 40 =1026
.
class Solution { public int sumNumbers(TreeNode root) { List<List<Integer>> res = new ArrayList(); List<Integer> cur = new ArrayList(); help(root, res, cur); int sum = 0; for(int i = 0; i < res.size(); i++){ int curr = 0; for(int j = 0; j < res.get(i).size(); j++){ curr = curr * 10 + res.get(i).get(j); } sum += curr; } return sum; } public void help(TreeNode root, List<List<Integer>> res, List<Integer> cur){ if(root == null) return; cur.add(root.val); if(root.left == null && root.right == null){ res.add(new ArrayList(cur)); } help(root.left, res, cur); help(root.right, res, cur); cur.remove(cur.size() - 1); } }
是113. path sumII的弱化版,本质是把所有遍历序列存到一个list(DFS),然后加在一起。cur是当前序列,每个数用完要remove掉防止重复。
public int sumNumbers(TreeNode root) { if (root == null) { return 0; } dfs(root, root.val); return sum; } int sum = 0; private void dfs(TreeNode root, int cursum) { //到达叶子节点 if (root.left == null && root.right == null) { sum += cursum; return; } //尝试左子树 if(root.left!=null){ dfs(root.left, cursum * 10 + root.left.val); } //尝试右子树 if(root.right!=null){ dfs(root.right, cursum * 10 + root.right.val); } }
另一种DFS,效率好像更高