【剑指 Offer】剑指 Offer 34. 二叉树中和为某一值的路径 （C++ dfs bfs 还原路径）

剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode） (leetcode-cn.com)

题意

找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

思路1

dfs，枚举每一条从根节点到叶子节点的路径，当遍历到叶子节点时，如果此时的路径和为目标值，则计入答案。

时间复杂度O（n^2）

代码1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>>ans;
    vector<int>path;
    
    void dfs(TreeNode* root,int target){
        if(root==nullptr) return ;
        path.push_back(root->val);
        target=target-root->val;
        if(root->left==nullptr&&root->right==nullptr&&!target){
            //是叶子节点并且目标值为0，说明此时路径上的和恰好为要求的值
            ans.push_back(path);
        }
        dfs(root->left,target);
        dfs(root->right,target);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root,target);
        return ans;
    }
};

思路2

还可以用bfs去做，bfs的难点就在于如何恢复路径。

一般最短路中都是维护前驱数组pre来还原路径，这里用哈希维护前驱pre，用于还原路径。

每次遍历到叶子节点并且当前路径和等于目标值，就还原路径。

还原路径时，循环，如果当前节点不为空，则将当前节点计入答案，当前节点等于父节点。最后翻转一下。因为还原的时候最开始的节点是叶子节点。

bfs中维护结点跟路径和的队列就行~

时间复杂度也是O（n^2）

代码2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>>ans;
    map<TreeNode*,TreeNode*>pre;
    
    void getPath(TreeNode* root){
        vector<int>tt;
        while(root!=nullptr){
            tt.push_back(root->val);
            root=pre[root];
        }
        reverse(tt.begin(),tt.end());
        ans.push_back(tt);
    }

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root==nullptr) return ans;
        queue<TreeNode*>q;
        queue<int>sum;
        q.push(root);
        sum.push(0);
        while(!q.empty()){
            TreeNode* now=q.front();q.pop();
            int res=sum.front()+now->val;sum.pop();
            if(now->left==nullptr&&now->right==nullptr){
                if(res==target){
                    getPath(now);
                }
            }else{
                if(now->left!=nullptr){
                    pre[now->left]=now;
                    q.push(now->left);
                    sum.push(res);
                }
                if(now->right!=nullptr){
                    pre[now->right]=now;
                    q.push(now->right);
                    sum.push(res);
                }
            }
            
        }
        return ans;
    }
};