题目

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

题解

这道题和113一样，可以用递归和迭代两种方法。这里再练习写一遍，详细题解见113

1. 递归法

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$ 需要额外空间。
class Solution {//两个方法。1.递归
vector<vector<int>> res;
public:
    void dfs(TreeNode* cur, int sum, vector<int> oneRes){
        if(!cur) return;
        oneRes.push_back(cur->val);
        if(!cur->left && !cur->right && cur->val==sum) res.push_back(oneRes);
        dfs(cur->left, sum-cur->val,oneRes);
        dfs(cur->right, sum-cur->val,oneRes);
        oneRes.pop_back();

    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> oneRes;
        dfs(root, sum, oneRes);
        return res;
    }
};

2. 栈迭代法

这个方法还不熟练，后面最好多做几遍

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$ 需要额外空间。
class Solution {//两个方法。2. 栈迭代
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        if(!root) return res;
        vector<TreeNode*> oneRes;
        auto cur = root;
        TreeNode* last = nullptr;
        int oneSum = 0;
        while(cur || !oneRes.empty()){
            while(cur){
                oneRes.push_back(cur);
                oneSum += cur->val;
                cur = cur->left;
            }
            auto tmp = oneRes.back();
            if(!tmp->left && !tmp->right && oneSum==sum){
                vector<int> thisRes;
                for(auto &o : oneRes) thisRes.push_back(o->val);
                res.push_back(thisRes);
            }
            if(tmp->right && tmp->right!=last){
                cur = tmp->right;
            }else{
                oneRes.pop_back();
                oneSum -= tmp->val;
                last = tmp;
            }

        }
        return res;
    }
};