题解 | #二叉树根节点到叶子节点和为指定值的路径#

深度优先搜索

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        if(!root) return {};
        vector<vector<int> > res;
        return dfs(res, root, sum);
    }
    vector<vector<int> >& dfs(vector<vector<int> >& res, TreeNode* root, int Sum){
        map<TreeNode*, bool> m; //是否访问过
        m[root] = true;
        vector<int> proc;
        int sum = 0;
        proc.push_back(root->val);
        sum += root->val;
        stack<TreeNode*> s;
        s.push(root);

        while(!s.empty()){
            TreeNode* cur = s.top();
            if(cur->left && m.find(cur->left) == m.end()){
                s.push(cur->left);
                m[cur->left] = true;
                sum += cur->left->val;
                proc.push_back(cur->left->val);
                continue;
            }
            if(cur->right && m.find(cur->right) == m.end()){
                s.push(cur->right);
                m[cur->right] = true;
                sum += cur->right->val;
                proc.push_back(cur->right->val);
                continue;
            }
            //走到叶子节点了
            if(sum == Sum)
                res.push_back(proc);
            //回溯
            do{
                cur = s.top();
                s.pop();
                sum -= proc.back();
                proc.pop_back();
            }while (!s.empty()&&
            (m.find(cur->left) == m.end() ||
            m.find(cur->right) == m.end()));
        }
        return res;
    }
};