剑指 Offer 34. 二叉树中和为某一值的路径

dfs

class Solution {
public: 
    vector<vector<int>> res;
    vector<int> tmp;
    void dfs(TreeNode *node, int target) {
        if(node == nullptr ) return;
        target -= node->val;
        tmp.emplace_back(node->val);

        if(node->left == nullptr && node->right == nullptr && target == 0){
            res.emplace_back(tmp);
        }

        dfs(node->left, target);
        dfs(node->right, target);
        tmp.pop_back(); // 恢复现场
    }

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root == nullptr) return {};

        dfs(root, target);
        return res;
    }
};

bfs

class Solution {
public:
    vector<vector<int>> ret;
    unordered_map<TreeNode*, TreeNode*> parent;

    void getPath(TreeNode* node) {
        vector<int> tmp;
        while(node != nullptr) {
            tmp.emplace_back(node->val);
            node = parent[node];
        }
        reverse(tmp.begin(), tmp.end());
        ret.emplace_back(tmp);
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root == nullptr) return ret;
        queue<TreeNode*> que_node;
        queue<int>que_sum;

        que_node.emplace(root);
        que_sum.emplace(0);

        while(!que_node.empty()){
            TreeNode *node = que_node.front();
            que_node.pop();
            int rec = que_sum.front() + node->val;
            que_sum.pop();
　　　　　　　　// 一定要注意这里的if else逻辑关系！
            if(node->left == nullptr && node->right == nullptr) {
                if(rec == target) getPath(node);
            }else{
                if(node->left != nullptr) {
                    parent[node->left] = node;
                    que_node.emplace(node->left);
                    que_sum.emplace(rec);
                }
                if(node->right != nullptr) {
                    parent[node->right] = node;
                    que_node.emplace(node->right);
                    que_sum.emplace(rec);
                }
            }
        }
        return ret;
    }
};