# [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.

#### 【代码】

/*********************************
*   日期：2014-12-30
*   作者：SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   来源：https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果：AC
*   来源：LeetCode
*   博客：
*   时间复杂度：O(n)
*   空间复杂度：O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int sumNumbers(TreeNode *root) {
if(root == NULL){
return 0;
}//if
return SumNumbers(root,0);
}
private:
int SumNumbers(TreeNode* node,int curSum){
if(node == NULL){
return 0;
}//if
curSum = curSum*10 + node->val;
// 到达叶子节点返回该路径上的值
if(node->left == NULL && node->right == NULL){
return curSum;
}
// 左子树
int leftSum = SumNumbers(node->left,curSum);
// 右子树
int rightSum = SumNumbers(node->right,curSum);
return leftSum + rightSum;
}
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
int len = num.size();
if(len == 0){
return NULL;
}//if
queue<TreeNode*> queue;
int index = 0;
// 创建根节点
TreeNode *root = new TreeNode(num[index++]);
// 入队列
queue.push(root);
TreeNode *p = NULL;
while(!queue.empty() && index < len){
// 出队列
p = queue.front();
queue.pop();
// 左节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *leftNode = new TreeNode(num[index]);
p->left = leftNode;
queue.push(leftNode);
}
index++;
// 右节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *rightNode = new TreeNode(num[index]);
p->right = rightNode;
queue.push(rightNode);
}
index++;
}//while
return root;
}

int main() {
Solution solution;
// -1代表NULL
vector<int> num = {1,2,3,4,-1,-1,5};
TreeNode* root = CreateTreeByLevel(num);
cout<<solution.sumNumbers(root)<<endl;
}


#### 【思路二】

/*---------------------------------------
*   日期：2015-05-08
*   作者：SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址：https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int sumNumbers(TreeNode* root) {
if(root == nullptr){
return 0;
}//if
queue<TreeNode*> nodeQueue;
queue<int> sumQueue;
nodeQueue.push(root);
sumQueue.push(0);

int curSum = 0;
int totalSum = 0;
TreeNode* node;
// 层次遍历
while(!nodeQueue.empty()){
// 当前节点
node = nodeQueue.front();
nodeQueue.pop();
// 当前路径和
curSum = sumQueue.front();
sumQueue.pop();
curSum = curSum * 10 + node->val;
// 左子结点
if(node->left){
nodeQueue.push(node->left);
sumQueue.push(curSum);
}//if
// 右子结点
if(node->right){
nodeQueue.push(node->right);
sumQueue.push(curSum);
}//if
// 叶子节点计算总和
if(node->left == nullptr && node->right == nullptr){
totalSum += curSum;
}//if
}//while
}
};


#### 【思路三】

/*---------------------------------------
*   日期：2015-05-08
*   作者：SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址：https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

// 二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int sumNumbers(TreeNode* root) {
if(root == nullptr){
return 0;
}//if
stack<TreeNode*> nodeStack;
nodeStack.push(root);
stack<int> sumStack;
sumStack.push(0);

TreeNode* node;
int curSum = 0;
int totalSum = 0;
// 先序遍历 非递归
while(!nodeStack.empty()){
// 当前节点
node = nodeStack.top();
nodeStack.pop();
// 当前路径和
curSum = sumStack.top();
sumStack.pop();
curSum = curSum * 10 + node->val;
// 右子节点
if(node->right){
nodeStack.push(node->right);
sumStack.push(curSum);
}//if
// 左子结点
if(node->left){
nodeStack.push(node->left);
sumStack.push(curSum);
}//if
// 叶子节点计算总和
if(node->left == nullptr && node->right == nullptr){
totalSum += curSum;
}//if
}//while
}
};

#### 【温故】

/*---------------------------------------
*   日期：2015-05-08
*   作者：SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   网址：https://leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int sumNumbers(TreeNode* root) {
if(root == nullptr){
return 0;
}//if
int curSum = 0;
int totalSum = 0;
helper(root,curSum,totalSum);
}
private:
void helper(TreeNode* root,int curSum,int &totalSum){
if(root == nullptr){
return;
}//if
// 先序遍历
curSum = curSum * 10 + root->val;
// 在叶子节点处计算总和
if(root->left == nullptr && root->right == nullptr){
totalSum += curSum;
return;
}//if
// 左子树
helper(root->left,curSum,totalSum);
// 右子树
helper(root->right,curSum,totalSum);
}
};

|
8月前
|

|
11月前
|

LeetCode - #2 Add Two Numbers

53 0
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
111 0
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
67 0
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
73 0
LeetCode 357. Count Numbers with Unique Digits

64 0
|

LeetCode 315. Count of Smaller Numbers After Self

75 0
|

52 0
Leetcode-Easy 985. Sum of Even Numbers After Queries
Leetcode-Easy 985. Sum of Even Numbers After Queries
80 0
|