题解 | #二叉树根节点到叶子节点的所有路径和#
二叉树根节点到叶子节点的所有路径和
http://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83
递归思想
通过题意可知，是要把从根节点到叶子节点的单一路径的数值进行拼接，拼成一个数，再把所有路径的数进行加和进行返回输出。
一般树的题都会想到的就是遍历，那么这个题也一样。首先定义一个函数，这个函数用来拼接数值以及计算加和。
拼接数值其实一句 sum=sum*10 + node->val就可以了，前提是sum初始值为0，也就是整棵树的根节点的父节点为0。那么当遍历到叶子节点后，返回sum的值即为拼接的数。之后递归遍历左、右子树，最终返回二者加和即可。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int dfs(TreeNode* node, int sum)
{
if(!node) return 0;
sum = sum*10 + node->val;
if(!node->left && !node->right)
{
return sum;
}
int sum_left = dfs(node->left,sum);
int sum_right = dfs(node->right,sum);
return sum_left+sum_right;
}
int sumNumbers(TreeNode* root) {
// write code here
return dfs(root,0);
}
};牛客刷题记录 文章被收录于专栏
记录自己的刷题记录，刷过的题的解法
查看29道真题和解析
