题解 | #二叉树根节点到叶子节点的所有路径和#
二叉树根节点到叶子节点的所有路径和
https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83
- 采用先序遍历
- 在遍历之外定义记录经过的路径path,路径之和sum
- 终止条件为叶子节点;本级函数:记录节点值,回溯时删除节点值;递推公式:递归遍历左右节点
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> #include <cmath> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ int sumNumbers(TreeNode* root) { // write code here vector<int> path; int sum = 0; if (root == nullptr) { return sum; } traversal(root, path, sum); return sum; } private: void traversal(TreeNode* root,vector<int>& path,int& sum) { path.push_back(root->val); if (root->left == nullptr && root -> right == nullptr) { int size = path.size(); for (int i=0; i<size; i++) { sum += path[i] * pow(10,size-i-1); } } if (root->left) { traversal(root->left,path,sum); } if (root->right) { traversal(root->right, path, sum); } path.pop_back(); } };