1 题目

给定一个二叉树和一个值sum，请找出所有的根节点到叶子节点的节点值之和等于sum 的路径.

2 解法

用递归的方法,如果当前不是叶子节点,就把sum减去当前的值,并把当前节点当作路径节点push进临时路径数组中,然后去检查其左右节点,如果是叶子节点的话,检查其值和剩下的sum值是否相等,如果相等就把已有的path当成结果之一放进最终result中:

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return int整型vector<vector<>> */ vector<vector<int>> res; vector<vector<int> > pathSum(TreeNode* root, int sum) { // write code here vector<int> path; if (root) { run(sum, root, path); } return res; } void run (int target, TreeNode* node, vector<int> path) { if (!node) return; path.push_back(node->val); if (node->left == nullptr && node->right == nullptr) { if (target == node->val) res.push_back(path); } else { target -= node->val; run(target, node->left, path); run(target, node->right, path); } } };