首页 > 代码库 > leetco Path Sum II
leetco Path Sum II
和上一题类似，这里是要记录每条路径并返回结果。
Given the below binary tree and sum = 22,
5 / 4 8 / / 11 13 4 / \ / 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5]]
我们用一个子函数来递归记录，知道叶子节点才判断是否有符合值，有的话就记录。需要注意的是递归右子树之前要把左子树的相应操作去除（见注释）。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void pathSum(TreeNode *root, vector<vector<int> > &ans, vector<int> tmp, int subsum, int sum) { if (!root) return ; if (!root -> left && !root -> right && subsum + root -> val == sum) { tmp.push_back(root -> val); ans.push_back(tmp); } if (root -> left) { tmp.push_back(root -> val); subsum += root -> val; pathSum(root -> left, ans, tmp, subsum, sum); tmp.pop_back(); //因为判断右子树的时候不需要左子树的和 subsum -= root -> val; } if (root -> right) { tmp.push_back(root -> val); subsum += root -> val; pathSum(root -> right, ans, tmp, subsum, sum); } } vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int> > ans; vector<int> tmp; pathSum(root, ans, tmp, 0, sum); return ans; }};
其实效率好一些的是对tmp传入引用，例如vector<int> &tmp，那么此时每次记录结果或者左右递归之后都要有一个pop值，来保证tmp符合当前的要求：详见
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void pathSum(TreeNode *root, vector<vector<int> > &ans, vector<int> &tmp, int subsum, int sum) { if (!root) return ; if (!root -> left && !root -> right && subsum + root -> val == sum) { tmp.push_back(root -> val); ans.push_back(tmp); tmp.pop_back(); // 保持tmp } if (root -> left) { tmp.push_back(root -> val); subsum += root -> val; pathSum(root -> left, ans, tmp, subsum, sum); tmp.pop_back(); // 因为判断右子树的时候不需要左子树的和 subsum -= root -> val; // 同上理 } if (root -> right) { tmp.push_back(root -> val); subsum += root -> val; pathSum(root -> right, ans, tmp, subsum, sum); tmp.pop_back(); // 保持tmp } } vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int> > ans; vector<int> tmp; pathSum(root, ans, tmp, 0, sum); return ans; }};
leetco Path Sum II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。