113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

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]
]

---

相比上一题LeetCode Path Sum更进一步，本题要把所有等于sum的路径记录下来，所以递归求解的时候要带着一个数组，把从根节点到当前节点的路径记录下来。常规题，完整代码如下：

class Solution {
public:
    void dfs(vector<vector<int> >& ans, vector<int>& path, int& target, int cur, TreeNode* root)
    {
        if (root->left == NULL && root->right == NULL) {
            if (cur + root->val == target) {
                path.push_back(root->val);
                ans.push_back(path);
                path.pop_back();
            }
            return;
        }
        if (root->left != NULL) {
            path.push_back(root->val);
            dfs(ans, path, target, cur + root->val, root->left);
            path.pop_back();
        }
        if (root->right != NULL) {
            path.push_back(root->val);
            dfs(ans, path, target, cur + root->val, root->right);
            path.pop_back();
        }
    }
    vector<vector<int> > pathSum(TreeNode* root, int sum)
    {
        vector<vector<int> > ans;
        if (root == NULL)
            return ans;
        vector<int> path;
        dfs(ans, path, sum, 0, root);
        return ans;
    }
};

本代码提交AC，用时16MS。
二刷。更简洁的代码，如下：

class Solution {
private:
    void dfs(vector<vector<int> >& ans, vector<int>& candidate, TreeNode* root, int sum)
    {
        candidate.push_back(root->val);
        sum -= root->val;
        if (root->left == NULL && root->right == NULL && sum == 0) {
            ans.push_back(candidate);
        }
        if (root->left != NULL)
            dfs(ans, candidate, root->left, sum);
        if (root->right != NULL)
            dfs(ans, candidate, root->right, sum);
        candidate.pop_back();
    }
public:
    vector<vector<int> > pathSum(TreeNode* root, int sum)
    {
        if (root == NULL)
            return {};
        vector<vector<int> > ans;
        vector<int> candidate;
        dfs(ans, candidate, root, sum);
        return ans;
    }
};

本代码提交AC，用时9MS。

三刷。更易读代码：

class Solution {
public:
	void dfs(TreeNode *root, vector<vector<int>> &ans, vector<int> &cand, int sum) {
		if (root->left == NULL && root->right == NULL && sum == 0) {
			ans.push_back(cand);
			return;
		}
		if (root->left != NULL) {
			cand.push_back(root->left->val);
			sum -= root->left->val;
			dfs(root->left, ans, cand, sum);
			sum += root->left->val;
			cand.pop_back();
		}
		if (root->right != NULL) {
			cand.push_back(root->right->val);
			sum -= root->right->val;
			dfs(root->right, ans, cand, sum);
			sum += root->right->val;
			cand.pop_back();
		}
	}
	vector<vector<int>> pathSum(TreeNode* root, int sum) {
		if (root == NULL)return {};
		vector<vector<int>> ans;
		vector<int> cand = { root->val };
		dfs(root, ans, cand, sum - root->val);
		return ans;
	}
};

本代码提交AC，用时12MS。