图和树的路径问题

图

一：用vector存储无向图

数据结构

const int N = 100;
vector<int> G[N];
void addEdge(int u, int v){
    // 无向图
    G[u].push_back(v);
    G[v].push_back(u);
}
int m; // 点的个数

创建图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

void printList(){
    for (int i = 0; i < m;i++){
        cout << i<<":";
        for (int j = 0; j < G[i].size();j++){
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
}
int main(){
    m = 7;
    addEdge(0, 6);
    addEdge(0, 3);
    addEdge(6, 5);
    addEdge(5, 4);
    addEdge(5, 1);
    addEdge(5, 3);
    addEdge(2, 1);
    addEdge(4, 2);
    printList();
    return 0;
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

深度优先遍历dfs

void _dfs(int x,vector<bool>& visited){//必须用引用&
    if(visited[x]) return;
    visited[x] = true;
    cout << x <<" ";
    // 访问x顶点的领接表
    for(auto &val:G[x]){
            _dfs(val, visited);
        }
    }
/*深度优先遍历dfs*/
void dfsTraverse(){
    vector<bool> visited(m, false);
    /*遍历图所有顶点*/
    for (int i = 0; i < m;i++){
        if(!visited[i]){
            _dfs(i, visited);
        }
    }
}

也可以不return，访问就直接设为true

void _dfs(int x,vector<bool>& visited){
    cout << x <<" ";
    // 访问x顶点的领接表
    for(auto &val:G[x]){
        if(!visited[val]){
            visited[val] = true;//设为以访问
            _dfs(val, visited);
        }
    }
    }
/*深度优先遍历dfs*/
void dfsTraverse(){
    vector<bool> visited(m, false);
    /*遍历图所有顶点*/
    for (int i = 0; i < m;i++){
        if(!visited[i]){
            visited[i] = true;//设为以访问
            _dfs(i, visited);
        }
    }
}

dfs结果：0 6 5 4 2 1 3

广度优先遍历bfs

void _bfs(int x,vector<bool>& visited){
    queue<int> que;
    que.push(x);
    while(!que.empty()){
        int tmp = que.front();
        que.pop();
        cout << tmp << " ";
        for(auto& val:G[tmp]){
            if(!visited[val]){
            visited[val] = true;
            que.push(val);
            }
        }
    }
}
/*广度优先遍历bfs*/
void bfsTraverse(){
    vector<bool> visited(m, false);
    /*遍历图所有顶点*/
    for (int i = 0; i < m;i++){
        if(!visited[i]){
            visited[i] = true;
            _bfs(i, visited);
        }
    }
}

或者写成一个函数

/*广度优先遍历bfs*/
void bfsTraverse()
{
    vector<bool> visited(m, false);
    /*遍历图所有顶点*/
    for (int i = 0; i < m; i++)
    {
        if (visited[i])  break;
        visited[i] = true;
        // 把领接表加入队列
        queue<int> que;
        que.push(i);
        while (!que.empty())
        {
            int tmp = que.front();
            que.pop();
            cout << tmp << " ";
            for (auto &val : G[tmp])
            {
                if (!visited[val])
                {
                    visited[val] = true;
                    que.push(val);
                }
            }
        }
    }
}

bfs结果：0 6 3 5 4 1 2

二：用vector存储有向图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

初始化图

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int N = 20;
//邻接表的信息：出度和权重
struct edge{
    int to;
    int w;
    edge(int to,int w):to(to),w(w){}
};
vector<edge> G[N];
void add_Edge(int u,int v,int w){
    G[u].push_back(edge(v, w));
}
int m;//顶点个数
void printList(){
    for (int i = 0; i < m;i++){
        cout << i << ":";
        for (auto &val : G[i]){
            cout << val.to << "(" << val.w << ")"<< " ";
        }
        cout << endl;
    }
}
int main(){
    m = 8;
    add_Edge(0,6,18);
    add_Edge(0,7,13);
    add_Edge(0,5,17);
    add_Edge(1,3,27);
    add_Edge(1,2,15);    
    add_Edge(3,5,16);    
    add_Edge(4,1,12);    
    add_Edge(6,4,26);
    printList();
    return 0;
}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

bfs和dfs

void dfs(int x,vector<bool>& visited){
    if(visited[x])
        return;
    visited[x] = true;
    cout << x << " ";
    for(auto& val:G[x]){
        dfs(val.to, visited);
    }
}
void dfsTraverse(){
    vector<bool> visited(m, false);
    for (int i = 0; i < m;i++){
        if(!visited[i]){
            dfs(i, visited);
        }
    }
}
void bfsTraverse(){
    vector<bool> visited(m, false);
    for (int i = 0; i < m;i++){
        if(!visited[i]){
            visited[i] = true;
            queue<int> que;
            que.push(i);
            while(!que.empty()){
                int tmp = que.front();
                que.pop();
                cout << tmp << " ";
                for(auto& val:G[tmp]){
                    if(!visited[val.to]){
                        visited[val.to] = true;
                        que.push(val.to);
                    }
                }
            }
        }
    }
}

dfs:0 6 4 1 3 5 2 7
bfs:0 6 7 5 4 1 3 2

三：求源到目的的所有路径

797. 所有可能的路径

dfs实现

本题规定起点是0，终点是graph.size()-1

由于没有环，所以不需要用数组记录当前结点是否已经访问过

思路就是从起点出发，遍历所有临界点（可选择的），然后进行dfs。

回到上一层循环，需要放弃该层节点的选择

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        this->graph = graph;
        int target = graph.size() - 1;
        ans.push_back(0);
        dfs(0, target);
        return res;
    }

private:
    vector<vector<int>> graph;
    vector<vector<int>> res;
    vector<int> ans;
    void dfs(int cur, int target) {
        if (cur == target) { //dfs的cur到达终点
            res.push_back(ans);
            return;
        }
        for (auto val : graph[cur]) {
            ans.push_back(val);
            dfs(val, target);
            //pop_back上一次选择的结点
            ans.pop_back();
        }
    }
};

或者先加节点再去判断是否结束递归

选用局部变量存ans，递归时候不同层不影响

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        this->graph = graph;
        int target = graph.size() - 1;
        vector<int> mm;
        dfs(0, target,mm);
        return res;
    }

private:
    vector<vector<int>> graph;
    vector<vector<int>> res;
    //注意：vector<int> ans不要加引用
    void dfs(int cur, int target,vector<int> ans) {
        ans.push_back(cur);
        //先加结点，再去判断
        if (cur == target) { 
            res.push_back(ans);
            return;
        }
        for (auto val : graph[cur]) {
            dfs(val, target,ans);
            //ans不同层不影响，不用pop
        }
    }
};

或者采用：

带有默认值0，首先加结点
class Solution {
public:
 vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
     this->graph = graph;
     int target = graph.size() - 1;
     dfs(target);
     return res;
 }

private:
 vector<vector<int>> graph;
 vector<vector<int>> res;
 vector<int> ans;
 void dfs(int target, int cur = 0) {
     ans.push_back(cur);
     // 先加结点，再去判断
     if (cur == target) {
         res.push_back(ans);
     } else {
         for (auto val : graph[cur]) {
             dfs(target, val);
             //ans.pop_back();
         }
     }
     ans.pop_back();
 }
};
else可以没有，因为cur==target后，target没有结点，else不会执行

这里的pop_back位置必须在下一次for(不同层之间)之前出现，也就是递归结束后要pop

可以在for内的ans之后

不能再else和for之间，因为递归结束后没pop

bfs实现

思路很简单：由于起点和终点确定，从起点依次把它的临接点路径加入最终结果，最后只输出终点的路径结果

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path;
        path.push_back(0);
        int target=graph.size()-1;//终点
        //队列存放路径，用vector<int>
        queue<vector<int>> que;
        que.push(path);
        while(!que.empty()){
            vector<int> tmp=que.front();
            que.pop();
            int cur=tmp.back();//考虑路径终点
            if(cur==target) res.push_back(tmp);
            /*遍历当前路径终点邻接点入队*/
            for(auto val:graph[cur]){
                tmp.push_back(val);
                que.push(tmp);//新路径入队
                tmp.pop_back();//不能影响for的同层结果
            }
        }
        return res;
    }
};

vector path;
path.push_back(0);
que.push(path);

等价于：que.push({0});

路径结果：

void printPath(vector<vector<int>> graph) {
     vector<int> path;
     path.push_back(0);
     int target = graph.size() - 1; // 终点
     // 队列存放路径，用vector<int>
     queue<vector<int>> que;
     que.push(path);
     while (!que.empty()) {
         vector<int> tmp = que.front();
         que.pop();
         /*遍历que*/
         for (auto val : tmp) {
             cout << val << " ";
         }
         cout << endl;
         /*遍历当前点邻接点*/
         int cur = tmp.back(); 
         for (auto val : graph[cur]) {
             vector<int> mm=tmp;
             mm.push_back(val); 
             que.push(mm); 
             //tmp.pop_back();新变量不用pop_back()
         }
     }
 }

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
在这里插入图片描述

四：求无向图的环

684. 冗余连接

dfs父节点找环法

下图：绿色是父节点，红色是当前结点，紫色背景代表结点以访问

由于dfs如果是树，那么只能通过父节点访问到该节点

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

    bool hascycle = false;
    void findPath(int v, int fa) {
        for (auto val : graph[v]) {
            // 从fa到达的val,回溯到val
            if (val == fa)
                continue;
            if (visit[val]) {
                hascycle = true;
                return;
            } else {
                visit[v] = true;//标记读过
                findPath(val, v);
                visit[v] = false;//回溯
            }
        }
    }

当然也可以先标记结点，回退上一层前把结点设置好

 bool hascycle = false;
    vector<vector<int>> graph;
    vector<bool> visit;
    void findPath(int v, int fa) {
        for (auto val : graph[v]) {
            // 从fa到达的val,回溯到val
            visit[v] = true; // 标记读过
            if (val != fa) {
                //输出结果
                if (visit[val]) {
                    hascycle = true;
                    return;
                } 
                findPath(val, v);
            }
            visit[v] = false; // 回溯
        }
    }

添加一个记录父节点的数组，就可以输出这个环

 vector<int> parent;
  //parent=vector<int>(n+1,-1);初始化-1
 void findPath(int v) {
     for (auto val : graph[v]) {
         // 从fa到达的val,回溯到val
         if (val == parent[v]) continue;
             //输出结果
             parent[val]=v;
             if (visit[val]) {
                 hascycle = true;
                 /*打印环*/
                 int tmp=v;
                 while(tmp!=val){
                     cout<<tmp<<" ";
                     tmp=parent[tmp];
                 }
                 cout<<tmp<<endl;
                 return;
             } 
             visit[v] = true; // 标记读过
             findPath(val);
             visit[v] = false; // 回溯
     }
 }

                  //也可以用do while
                   do{
                       cout<<tmp<<" ";
                       tmp=parent[tmp];
                    }while(tmp!=val);

本题就是，每次增加一条边，然后对图进行遍历，当新加入的边使得图成环，则该边为所求。

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        // 题目是树多了一条边
        int n = edges.size();
        // 顶点从1开始，所以下标到n
        visit = vector<bool>(n + 1, false);
        graph = vector<vector<int>>(n + 1, vector<int>());
        for (auto val : edges) {
            int u = val[0];
            int v = val[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
            findPath(u, -1);//起点必须为u，不然可能不是连通图
            if (hascycle)
                return val;
        }
        return {};
    }

private:
    bool hascycle = false;
    vector<vector<int>> graph;
    vector<bool> visit;
    void findPath(int v, int fa) {
        for (auto val : graph[v]) {
            // 从fa到达的val,回溯到val
            if (val != fa) {
                //输出结果
                if (visit[val]) {
                    hascycle = true;
                    return;
                } 
                visit[v] = true; // 标记读过
                findPath(val, v);
                visit[v] = false; // 回溯
            }
        }
    }
};

五：树的路径问题

129. 求根节点到叶节点数字之和

广度优先遍历

队列要存放两个信息（当前节点，和当前节点的路径和），可以选择pair对或者两个队列分别存放

另外本题注意：数字序列12表示先访问1再访问2，所以新节点值加入结果前，原结果乘10

  int sumNumbers(TreeNode* root) {
        using pr=pair<TreeNode*,int>;
        int res=0;
        if(root==NULL) return res;
        //定义存放结点和路径和的队列
        queue<pr> que;
        que.push({root,root->val});
        while(!que.empty()){
            auto [node,val]=que.front();
            que.pop();
            //叶子结点累加val值
            if(!node->left && !node->right){
                res+=val;
            }
            if(node->left){
                que.push({node->left,val*10+node->left->val});
            }
            if(node->right){
                que.push({node->right,val*10+node->right->val});
            }
        }
        return res;
    }

也可以选用两个队列

 int sumNumbers(TreeNode* root) {
        int res=0;
        if(root==NULL) return res;
        //定义存放结点队列que1和路径和的队列que2
        queue<TreeNode*> que1;
        queue<int> que2;
        que1.push(root);
        que2.push(root->val);
        while(!que1.empty()){
            auto node=que1.front();
            auto val=que2.front();
            que1.pop();
            que2.pop();
            //叶子结点累加val值
            if(!node->left && !node->right){
                res+=val;
            }
            if(node->left){
                que1.push(node->left);
                que2.push(val*10+node->left->val);
            }
            if(node->right){
                que1.push(node->right);
                que2.push(val*10+node->right->val);
            }
        }
        return res;
    }

深度优先遍历

如果是全局变量，注意要恢复

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        dfs(root);
        return sum;
    }
private:
    int sum=0;
    int cur=0;
    void dfs(TreeNode* root){
        if(root==NULL) return;
        //root不空
        cur=cur*10+root->val;
        //叶子节点存结果
        if(!root->left && !root->right){
            sum+=cur;
        }
        dfs(root->left);
        dfs(root->right);
        //回退节点，去掉cur回退值
        cur=(cur-root->val)/10;
    }
};

而局部变量则不需要考虑回退

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        dfs(root,0);
        return sum;
    }
private:
    int sum=0;
    void dfs(TreeNode* root,int cur){
        if(root==NULL) return;
        //root不空
        cur=cur*10+root->val;
        //叶子节点存结果
        if(!root->left && !root->right){
            sum+=cur;
        }
        dfs(root->left,cur);
        dfs(root->right,cur);
    }
};

借助int返回值

class Solution {
public:
    int sumNumbers(TreeNode* root) {
       return rec(root,0);
    }
private:
    int rec(TreeNode* root,int cur) {
        if(root==NULL) return 0;
        //叶子节点
        cur=cur*10+root->val;
        if(!root->left && !root->right){
              return cur;
        }else{//左右子树有一个
             return rec(root->left,cur)+rec(root->right,cur);
        }
    }
};

257. 二叉树的所有路径

广度优先遍历

数字转成字符串：to_string()
字符串（数字）转成数字：stoi()

vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        using pr=pair<TreeNode*,string>;
        queue<pr> que;
        que.push({root,to_string(root->val)});
        while(!que.empty()){
            auto [k,v]=que.front();
            que.pop();
            //存结果
            if(!k->left && !k->right){
                res.push_back(v);
            }
            //注意更新左右孩子的v
            if(k->left){
                que.push({k->left,v+"->"+to_string(k->left->val)});
            }
            if(k->right){
                que.push({k->right,v+"->"+to_string(k->right->val)});
            }
        }
        return res;
    }

也可以用栈（先序遍历）

 vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        using pr=pair<TreeNode*,string>;
        stack<pr> sta;
        sta.push({root,to_string(root->val)});
        while(!sta.empty()){
            auto [k,v]=sta.top();
            sta.pop();
            //存结果
            if(!k->left && !k->right){
                res.push_back(v);
            }
            //注意栈后进先出，先右后左
            if(k->right){
                sta.push({k->right,v+"->"+to_string(k->right->val)});
            }
            if(k->left){
                sta.push({k->left,v+"->"+to_string(k->left->val)});
            }
        }
        return res;
    }

深度优先遍历

这里由于数字存在负数，而且还存在->，回退比较难，最好不用全局变量

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root,"");
        return res;
    }
private:
    vector<string> res;
    void dfs(TreeNode* root,string path){
        if(root==NULL) return;
        path+=to_string(root->val);
        if(!root->left && !root->right){
            res.push_back(path);
        }
        //可以没有判断，因为不存在 NULL->内容
            dfs(root->left,path+"->");
            dfs(root->right,path+"->");
    }
};

或者提前判断好，更新结果

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==NULL) return res;
        dfs(root,to_string(root->val));
        return res;
    }
private:
    vector<string> res;
    void dfs(TreeNode* root,string path){
        if(root==NULL) return;
        if(!root->left && !root->right){
            res.push_back(path);
        }
        if(root->left){
            dfs(root->left,path+"->"+to_string(root->left->val));
        }
        if(root->right){
            dfs(root->right,path+"->"+to_string(root->right->val));
        }
    }
};

分治

vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root==NULL) return res;
        if(!root->left && !root->right){
            res.push_back(to_string(root->val));
            return res;//可以回退了
        }
        //分别求左右子树结果
        vector<string> leftPath=binaryTreePaths(root->left);
        vector<string> rightPath=binaryTreePaths(root->right);
        //合并结果
        for(auto val:leftPath){
            res.push_back(to_string(root->val)+"->"+val);
        }
        for(auto val:rightPath){
            res.push_back(to_string(root->val)+"->"+val);
        }
        return res;
    }

每个路径结果=当前节点+左子树结果+右子树结果

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

测试：

     if(!root->left && !root->right){
         res.push_back("("+to_string(root->val)+")");
         return res;//提前结束
     }
     for(auto aa:leftSide){
         res.push_back(to_string(root->val)+"左"+aa+"左"+to_string(root->val));
     }
     for(auto bb:rightSide){
         //cout<<bb<<endl;
         res.push_back(to_string(root->val)+"右"+bb+"右"+to_string(root->val));
     }
     cout<<endl;
     for(auto xx:res){
         cout<<xx<<";";
     }
     cout<<endl;

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

112. 路径总和

利用bool

 bool hasPathSum(TreeNode* root, int targetSum) {
         if(root==NULL) return false;
         if(!root->left && !root->right && root->val==targetSum){
            return true;
         }
         return hasPathSum(root->left,targetSum-root->val)||\
                hasPathSum(root->right,targetSum-root->val);
    }

当然也可以把中间改成：

 if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }

如果对返回值不敏感，则设立全局变量

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        dfs(root,targetSum);
        return hasAns?true:false;
    }
private:
    bool hasAns=false;
    void dfs(TreeNode* root ,int target){
        if(root==NULL) return;
        if(!root->left &&!root->right && root->val==target){
            hasAns=true;
            return;
        }
        //root肯定存在
        dfs(root->left,target-root->val);
        dfs(root->right,target-root->val);
    }
};

113. 路径总和 II

深度优先遍历

全局变量，需要回溯

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        this->target=targetSum;
        dfs(root);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> path;
    int sum=0;
    int target;
    void dfs(TreeNode* root){
         if(root==NULL) return;
         path.push_back(root->val);
         sum+=root->val;
         //满足结果：叶子+值符合要求
         if(!root->left && !root->right && sum==target){
             res.push_back(path);
         }
         dfs(root->left);
         dfs(root->right);
         //回溯
         path.pop_back();
         sum-=root->val;
    }
};

也可以改成局部变量

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        this->target=targetSum;
        dfs(root,{},0);
        return res;
    }
private:
    vector<vector<int>> res;
    int target;
    void dfs(TreeNode* root,vector<int> path,int sum){
         if(root==NULL) return;
         path.push_back(root->val);
         sum+=root->val;
         //满足结果：叶子+值符合要求
         if(!root->left && !root->right && sum==target){
             res.push_back(path);
         }
         dfs(root->left,path,sum);
         dfs(root->right,path,sum);
    }
};

当然也可以用减法去判断

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root,{},targetSum);
        return res;
    }
private:
    vector<vector<int>> res;
    void dfs(TreeNode* root,vector<int> path,int target){
         if(root==NULL) return;
         path.push_back(root->val);
         target-=root->val;
         //满足结果：叶子+值符合要求
         if(!root->left && !root->right && target==0){
             res.push_back(path);
         }
         dfs(root->left,path,target);
         dfs(root->right,path,target);
    }
};

广度优先遍历

这里需要存储三个元素：节点，路径和余下值，由于pair是二元组，存储三个元素要么pair复合使用，要么使用tuple

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        using tup = tuple<TreeNode*, vector<int>, int>;
        queue<tup> que;
        //根节点存在
        que.push({root, {root->val}, targetSum-root->val});
        while (!que.empty()) {
            auto [node, path, val] = que.front();
            que.pop();
            if (!node->left && !node->right && val ==0) {
                res.push_back(path);
            }
            if (node->left) {
                path.push_back(node->left->val);
                que.push({node->left, path, val- node->left->val});
                path.pop_back();
            }
            if (node->right) {
                path.push_back(node->right->val);
                que.push({node->right, path, val- node->right->val});
                path.pop_back();
            }
        }
        return res;
    }
};

不回溯就用局部变量

          if (node->left) {
                vector<int> tmp1 = path;//局部变量
                tmp1.push_back(node->left->val);
                que.push({node->left, tmp1, val - node->left->val});
            }
            if (node->right) {
                vector<int> tmp2 = path;//局部变量
                tmp2.push_back(node->right->val);
                que.push({node->right, tmp2, val - node->right->val});
            }

使用两次pair

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        /*使用两次pair*/
        using pr=pair< TreeNode*,vector<int>>;
        queue<pair<pr,int>> que;
        que.push({{root,{root->val}},targetSum-root->val});
        while(!que.empty()){
            auto [tmp,tar]=que.front();
            que.pop();
            auto [k,v]=tmp;//相当于tmp.first和tmp.second
            if(!k->left && !k->right && tar==0){
                res.push_back(v);
            }
            if(k->left){
                v.push_back(k->left->val);
                que.push({{k->left,v},tar-k->left->val});
                v.pop_back();
            }
            if(k->right){
                v.push_back(k->right->val);
                que.push({{k->right,v},tar-k->right->val});
                v.pop_back();
            }
        }
        return res;
    }
};

或者在while进行路径选择

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        using tup = tuple<TreeNode*, vector<int>, int>;
        queue<tup> que;
        // 根节点存在
        que.push({root, {}, targetSum});
        while (!que.empty()) {
            auto [node, path, val] = que.front();
            que.pop();
            if(node==NULL) return res;
            //在这里加入路径
            path.push_back(node->val);
            if (!node->left && !node->right && val == node->val) {
                res.push_back(path);
            }
            if (node->left) {
                que.push({node->left, path, val - node->val});
            }
            if (node->right) {
                que.push({node->right, path, val - node->val});
            }
        }
        return res;
    }
};

或者不存储路径信息，但是用map存储父节点，然后通过节点追溯父节点得到路径

由于从叶子追溯到跟正好是路径的逆序，存储路径前需要reverse一下

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        using pr = pair<TreeNode*, int>;
        queue<pr> que;
        // 根节点存在
        if(root==NULL) return res;
        que.push({root, targetSum-root->val});
        while (!que.empty()) {
            auto [node, val] = que.front();
            que.pop();
            if (!node->left && !node->right && val == 0) {
                 getPath(node);
            }
            if (node->left) {
                mp[node->left]=node;
                que.push({node->left, val - node->left->val});
            }
            if (node->right) {
                mp[node->right]=node;
                que.push({node->right, val - node->right->val});
            }
        }
        return res;
    }
private:
    vector<vector<int>> res;
    //记录父节点
    //由于题目没说值不同，所以存Treenode*
    unordered_map<TreeNode*,TreeNode*> mp;
    void getPath(TreeNode* t){
         TreeNode* tmp=t;
         vector<int> ans;
         while(tmp){
             ans.push_back(tmp->val);
             tmp=mp[tmp];
         }
         reverse(ans.begin(),ans.end());
         res.push_back(ans);
    }
};

也可以：把路径存到{}中

void getPath(TreeNode* t,vector<int> ans)
getPath(node,{});

437. 路径总和 III

这里：起点不同，但是必须是在自己的子树下面查找，也就是更换根，然后借助函数去找路径

注意更换根一定要在主函数内完成，因为这样才能达到改变根的目的。

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(root==NULL) return 0;
        //从根节点找
        int ret=_dfs(root,targetSum);
        //改变左右子树
        ret+=pathSum(root->left,targetSum);
        ret+=pathSum(root->right,targetSum);
        return ret;
    }
private:
    int _dfs(TreeNode* cur,long target){
        //从当前cur作为根节点去找路径
        if(cur==NULL) return 0;
        int res=0;
        //储存结果
        if(cur->val==target) res++;
        res+=_dfs(cur->left,target-cur->val);
        res+=_dfs(cur->right,target-cur->val);
        return res;
    }
};

在_dfs主要改变target值
在pathSum主要改变根节点root

注意测试用例int溢出，所以用long

可以写成一句话

return res+_dfs(cur->left,target-cur->val)+_dfs(cur->right,target-cur->val);

精简写法：

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
       if(root==NULL) return 0;
       return dfs(root,targetSum)+\
           pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
    }
private:
    int dfs(TreeNode* node,long sum){
        if(node==NULL) return 0;
        int res=0;
        res+=(node->val==sum)?1:0;
        return res+dfs(node->left,sum-node->val)+dfs(node->right,sum-node->val);       
    }
};

树上前缀和

树的前缀有两种：

一种是起点是根节点，终点是任意节点（自顶向下）
一种是起点是各个叶子节点，然后到达任意节点（自底向上）

自顶向下是各个儿子节点加上根节点，自底向上是节点是自己值加上其所有儿子节点

具体又分为点权和边权，也就是点是值或者点无值边是权

自顶向下的点权：

自顶向下的边权（根节点视为0，边归为下一个节点）

自底向上的点权

本题中：

前缀和为：

用map存储值和频次 : map[和]=次数

其实相当于一次看一个分支：

需要加上0，才能包含根节点,即：mp[0]=1

0—>10->15->18->21----21-10就是：5->3->3

0—>10->15->18->16----找和为1，看sum-target在mp中是否存在

0—>10->15->17->18

0—>10->7->18

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        this->target=targetSum;
        mp[0]=1;//这里是为了包含根节点
        dfs(root);
        return res;
    }
private:
    int target;
    int res=0;
    long sum=0;//用int累加会溢出
    //mp[sum]=频次
    unordered_map<long,int> mp;
    void dfs(TreeNode* root){
        if(root==NULL) return;
        sum+=root->val;
        //存结果
        if(mp.count(sum-target)){// if(mp[sum-target]>0)
            res+=mp[sum-target];
        }
        //更新频次
        mp[sum]++;
        dfs(root->left);
        dfs(root->right);
        //回溯
        //一定要先将mp[sum]-1再减去sum
        mp[sum]--;
        sum-=root->val;
    }
};

由于回溯，其实map只统计一条路径的前缀和和频次

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传