题解 | #二叉树根节点到叶子节点的所有路径和#
二叉树根节点到叶子节点的所有路径和
http://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83
题目：二叉树根节点到叶子节点的所有路径和
描述：给定一个仅包含数字0−9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。例如根节点到叶子节点的一条路径是1→2→3,那么这条路径就用123来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：这颗二叉树一共有两条路径，根节点到叶子节点的路径1→2用数字12代替，根节点到叶子节点的路径1→3用数字13代替，所以答案为12+13=25。
示例1：输入：{1,0}，返回值：10
解法一：
思路分析：通过题目分析，我们可以将每条根节点到叶子结点的路径和用一个数字代替，如果向下一个结点，就将之前的数字都左移一位，通过使用dfs找到左右子树的所有路径，最后回溯求和，得到最后的结果值。
实例分析：根节点到叶子节点的一条路径是1→2→3。
| 数字 | 1 | 2 | 3 |
| sum = sum * 10 + root->val; | |||
| 第一步 | Sum = 0 * 10 + 1 | ||
| 第二步 | 判断2和3结点是否为1的子结点 | ||
| 第三步 | Sum = 1 * 10 + 2 + 1 * 10 + 3 = 25 | ||
| 最后输出结果值为25 | |||
具体C++代码为：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int sumNumbers(TreeNode* root) {
// write code here
if(!root)//特殊情况
return 0;
int sum = 0;
return preorder(root, sum);
}
int preorder(TreeNode* root, int sum){
if(root == NULL)
return 0;
sum = sum * 10 + root->val;//一层一层进行遍历
if(!root->left && !root->right)//没有子结点
return sum;
return preorder(root->left, sum) + preorder(root->right, sum);
}
};
思路分析：我们也可以通过在vector中保存路径来计算结果，将根节点到叶子节点的路径记录到paths中，通过计算得到最终的结果。
具体C++代码如下所示：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int sumNumbers(TreeNode* root) {
// 通过在vector中保存路径来计算结果
if(root == nullptr)
return 0;
vector temp;
vector paths;
path(temp, root, paths);
//对paths里记录的内容进行求和
int sum = 0; //最终结果
for(auto &i : paths){
int line = 0; //记录单个路径的和
for(auto &j : i){
line = line*10+j;
}
sum += line;
}
return sum;
}
void path(vector&temp, TreeNode* root, vector &paths){
if(root == nullptr)
return;
temp.push_back(root->val);
if(root->left==nullptr && root->right==nullptr)
paths.push_back(temp); //将根节点到叶子节点的一个路径记录到paths中
if(root->left)
path(temp, root->left, paths);
if(root->right)
path(temp, root->right, paths);
temp.pop_back();
}
}; 在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。
投递传音控股等公司8个岗位 >
