【题目】
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
return totalSum;
}
};
层次遍历，对与每个节点都要记住父节点的当前和。因为计算每个节点的当前和都会因父节点而不一样。
到达叶子节点代表一条路径的结束。这个当前和加入到总和中。
【思路三】
先序遍历的非递归版本
/*---------------------------------------
* 日期：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
return totalSum;
}
};
【温故】
/*---------------------------------------
* 日期：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);
return 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);
}
};
LeetCode 124. Binary Tree Maximum Path Sum
