[LeetCode]129.Sum Root to Leaf Numbers

本文主要是介绍[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;}//ifreturn SumNumbers(root,0);}
private:int SumNumbers(TreeNode* node,int curSum){if(node == NULL){return 0;}//ifcurSum = 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;}//ifqueue<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++;}//whilereturn root;
}int main() {Solution solution;// -1代表NULLvector<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;}//ifqueue<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}//whilereturn 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;}//ifstack<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}//whilereturn 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;}//ifint 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]129.Sum Root to Leaf Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---