|
| 1 | +/* |
| 2 | + Author: King, wangjingui@outlook.com |
| 3 | + Date: Jan 02, 2014 |
| 4 | + Problem: Sum Root to Leaf Numbers |
| 5 | + Difficulty: Easy |
| 6 | + Source: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ |
| 7 | + Notes: |
| 8 | + Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. |
| 9 | + An example is the root-to-leaf path 1->2->3 which represents the number 123. |
| 10 | + Find the total sum of all root-to-leaf numbers. |
| 11 | + For example, |
| 12 | + 1 |
| 13 | + / \ |
| 14 | + 2 3 |
| 15 | + The root-to-leaf path 1->2 represents the number 12. |
| 16 | + The root-to-leaf path 1->3 represents the number 13. |
| 17 | + Return the sum = 12 + 13 = 25. |
| 18 | +
|
| 19 | + Solution: 1. Recursion (add to sum when reaching the leaf). |
| 20 | + 2. Iterative solution. |
| 21 | + */ |
| 22 | + |
| 23 | +/** |
| 24 | + * Definition for binary tree |
| 25 | + * struct TreeNode { |
| 26 | + * int val; |
| 27 | + * TreeNode *left; |
| 28 | + * TreeNode *right; |
| 29 | + * TreeNode(int x) : val(x), left(NULL), right(NULL) {} |
| 30 | + * }; |
| 31 | + */ |
| 32 | +classSolution { |
| 33 | +public: |
| 34 | +intsumNumbers(TreeNode *root) { |
| 35 | +returnsumNumbers_1(root); |
| 36 | + } |
| 37 | + |
| 38 | +intsumNumbers_1(TreeNode *root) { |
| 39 | +intsum =0; |
| 40 | +sumNumbersRe(root,0,sum); |
| 41 | +returnsum; |
| 42 | + } |
| 43 | + |
| 44 | +voidsumNumbersRe(TreeNode *node,intnum,int &sum) { |
| 45 | +if (!node)return; |
| 46 | +num =num *10 +node->val; |
| 47 | +if (!node->left && !node->right) { |
| 48 | +sum +=num; |
| 49 | +return; |
| 50 | + } |
| 51 | +sumNumbersRe(node->left,num,sum); |
| 52 | +sumNumbersRe(node->right,num,sum); |
| 53 | + } |
| 54 | + |
| 55 | +intsumNumbers_2(TreeNode *root) { |
| 56 | +if (!root)return0; |
| 57 | +intres =0; |
| 58 | +queue<pair<TreeNode *,int>>q; |
| 59 | +q.push(make_pair(root,0)); |
| 60 | +while(!q.empty()) |
| 61 | + { |
| 62 | +TreeNode *node =q.front().first; |
| 63 | +intsum =q.front().second *10 +node->val; |
| 64 | +q.pop(); |
| 65 | +if (!node->left && !node->right) |
| 66 | + { |
| 67 | +res +=sum; |
| 68 | +continue; |
| 69 | + } |
| 70 | +if (node->left) |
| 71 | +q.push(make_pair(node->left,sum)); |
| 72 | +if (node->right) |
| 73 | +q.push(make_pair(node->right,sum)); |
| 74 | + } |
| 75 | +returnres; |
| 76 | + } |
| 77 | +}; |
