【LeetCode】129. 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.

For example,

    1
   / 
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题解：

　　类似于 Path Sum 和 Path Sum II，迭代方法依然是后序遍历的思路，先遍历左右孩子。

Solution 1

 1 class Solution {
 2 public:
 3     int sumNumbers(TreeNode* root) {
 4         if (!root)
 5             return 0;
 6         return dfs(root, 0);
 7     }
 8     int dfs(TreeNode* root, int sum) {
 9         if (!root)
10             return 0;
11         sum = sum * 10 + root->val;
12         if (!root->left && !root->right)
13             return sum;
14         return dfs(root->left, sum) + dfs(root->right, sum);
15     }
16 };

Solution 2

 1 class Solution {
 2 public:
 3     int sumNumbers(TreeNode* root) {
 4         if (!root)
 5             return 0;
 6         queue<TreeNode*> q1;
 7         queue<int> q2;
 8         q1.push(root);
 9         q2.push(root->val);
10         
11         int sum = 0, cursum = 0;
12         TreeNode* cur = root;
13         
14         while (!q1.empty()) {
15             cur = q1.front();
16             cursum = q2.front();
17             q1.pop();
18             q2.pop();
19             
20             if (!cur->left && !cur->right) {
21                 sum += cursum;
22             }
23             if (cur->left) {
24                 q1.push(cur->left);
25                 q2.push(cursum * 10 + cur->left->val);
26             }
27             if (cur->right) {
28                 q1.push(cur->right);
29                 q2.push(cursum * 10 + cur->right->val);
30             }
31         }
32         return sum;
33     }
34 };

Solution 3

 1 class Solution {
 2 public:
 3     int sumNumbers(TreeNode* root) {
 4         if (!root)
 5             return 0;
 6         stack<TreeNode*> s1;
 7         stack<int> s2;
 8         int sum = 0, cursum = 0;
 9         TreeNode* cur = root, *pre = nullptr;
10         while (cur || !s1.empty()) {
11             while (cur) {
12                 s1.push(cur);
13                 cursum = cursum * 10 + cur->val;
14                 s2.push(cursum);
15                 cur = cur->left;
16             }
17             cur = s1.top();
18             if (!cur->left && !cur->right) {
19                 sum += cursum;
20             }
21             if (cur->right && cur->right != pre) {
22                 cur = cur->right;
23             } else {
24                 pre = cur;
25                 s1.pop();
26                 cursum = s2.top();
27                 s2.pop();
28                 cursum -= cur->val;
29                 cursum /= 10;
30                 cur = nullptr;
31             }
32         }
33         return sum;
34     }
35 };