113. Path Sum II

冷不防 2022-03-26 09:26 197阅读 0赞

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

方法一：迭代

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		vector<vector<int>> result;
    		vector<int> res;
    
    		if (root == NULL)
    			return result;
    		stack<TreeNode*> stackNode;
    		TreeNode* pre = NULL;
    		int count = 0;
    		while (root != NULL || !stackNode.empty())
    		{
    			while (root)
    			{
    				stackNode.push(root);
    				res.push_back(root->val);
    				count += root->val;
    				root = root->left;
    			}
    			TreeNode* temp = stackNode.top();
    			if (temp->right != NULL && temp->right != pre)
    			{
    				root = temp->right;
    				continue;
    			}
    
    			if (temp->left == NULL && temp->right == NULL && count == sum)
    			{				
    				result.push_back(res);
    			}
    			stackNode.pop();
    			res.pop_back();
    			pre = temp;
    			count -= temp->val;	
    			root = NULL;
    		}
    		return result;
    	}
    };

方法二：递归

/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    class Solution {
    public:
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		vector<int> res;
    		if (root == NULL)
    			return result;
    		helper(root, res, 0, sum);
    		return result;
    	}
    
    private:
    	vector<vector<int>> result;
    	void helper(TreeNode* root, vector<int> temp, int cur, int sum)
    	{
    		if (root == NULL)
    			return;
    		temp.push_back(root->val);
    		if (root->left == NULL && root->right == NULL && cur + root->val == sum)
    		{
    			result.push_back(temp);
    			return;
    		}
    
    		helper(root->left, temp, root->val + cur, sum);
    		helper(root->right, temp, root->val + cur, sum);
    	}
    };