题解 | #二叉树根节点到叶子节点的所有路径和#
二叉树根节点到叶子节点的所有路径和
http://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83
本题和求二叉树中是否存在节点和为指定值的路径那道题一样,比较简单的思路是通过一次前序遍历,将每一步走过的值存起来,等走到叶子节点时,计算该路径所对应的路径和,然后再用一个sum将每一条路径的和都加起来。
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ void SumNodes(TreeNode* root,int& sum ,vector<int> arr){ if(!root) { return ; } arr.push_back(root->val); if(!root->left&&!root->right&&arr.size()!=0){ int tmp=0; for(int i=0;i<arr.size();i++){ tmp=tmp+(arr[i])*pow(10,arr.size()-i-1); } sum+=tmp; return; } if(root->left) SumNodes(root->left,sum,arr); if(root->right) SumNodes(root->right,sum,arr); } int sumNumbers(TreeNode* root) { // write code here if(!root) return 0; vector<int> arr; int sum=0; SumNodes(root,sum,arr); return sum; } };