1. Toy模板网首页
  2. > Toy博客

二叉树与图（C++刷题笔记）

9月前 作者：Rkun18 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了二叉树与图（C++刷题笔记）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树与图（C++刷题笔记）

113. 路径总和 II

力扣

  • 从根节点深度遍历二叉树，先序遍历时，将节点存储至path栈中，使用path_val累加节点值

  • 当遍历到叶子节点，检查path_val是否为sum，若是，则将pathpush进入res的结果中去

  • 在后续变量，将该节点从path栈中弹出，path_val减去节点值

题目代码

/**
 * 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>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int> >res;
        vector<int>path;
        int path_val=0;
        preorder(root,path_val,targetSum,path,res);
        return res;

    }
    void preorder(TreeNode *nd,int &path_val,int sum,vector<int>&path,vector<vector<int> >&res){
        if(!nd)return;
        path_val+=nd->val;
        path.push_back(nd->val);
        if(!nd->right&&!nd->left&&path_val==sum){
            res.push_back(path);
        }
        preorder(nd->left,path_val,sum,path,res);
        preorder(nd->right,path_val,sum,path,res);
        path_val-=nd->val;
        path.pop_back();

    }

};

236. 二叉树的最近公共祖先

力扣

  • 两个节点公共祖先一定从根节点，至这两个节点的路径上

  • 由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路径上的里根几点最远的节点

  • 求两个节点路径最后一个相同的节点

求根节点到某一个节点的路径

  • 从根节点遍历至该节点，找到节点后就结束搜索

  • 将遍历过程中遇到的节点按顺序存储，节点即路径

  void dfs(TreeNode *nd,TreeNode *search,vector<TreeNode *>&path,vector<TreeNode *>&res,int &end){
        if(!nd||end==1)return;
        path.push_back(nd);
        if(nd==search){
            end=1;
            res=path;
        }
        dfs(nd->left,search,path,res,end);
        dfs(nd->right,search,path,res,end);
        path.pop_back();
    }

求两路径下最后一个相同节点

  • 求出较短路径长度n

  • 同时遍历p节点与q节点路径，遍历n个节点，最后一个相同的节点即最近公共祖先

题目代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode *>path;
        vector<TreeNode *>p_path;
        vector<TreeNode *>q_path;
        int end=0;
        dfs(root,p,path,p_path,end);
        path.clear();
        end=0;
        dfs(root,q,path,q_path,end);
        int path_len=0;
        if(p_path.size()<q_path.size()){
            path_len=p_path.size();
        } else{
            path_len=q_path.size();
        }

        TreeNode *res=NULL;
        for (int i = 0; i < path_len; ++i) {
            if(p_path[i]==q_path[i]){
                res=p_path[i];
            }
        }
        return res;


    }
    void dfs(TreeNode *nd,TreeNode *search,vector<TreeNode *>&path,vector<TreeNode *>&res,int &end){
        if(!nd||end==1)return;
        path.push_back(nd);
        if(nd==search){
            end=1;
            res=path;
        }
        dfs(nd->left,search,path,res,end);
        dfs(nd->right,search,path,res,end);
        path.pop_back();
    }
};

114. 二叉树展开为链表

力扣

  • 前序遍历二叉树，将指针push进入vector，顺序遍历vector中节点，链接相邻两节点
/**
 * 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:
    void flatten(TreeNode* root) {
        vector<TreeNode *>vec;
        preorder(root,vec);
        for (int i = 1; i <vec.size(); ++i) {
            vec[i-1]->left=NULL;
            vec[i-1]->right=vec[i];
        }

    }
    void preorder(TreeNode *nd,vector<TreeNode *>&vec){
        if(!nd)return;
        vec.push_back(nd);
        preorder(nd->left,vec);
        preorder(nd->right,vec);
    }
};

199. 二叉树的右视图

  • 从二叉树的右侧观察它，将观察到的节点从上到下顺序输出，就是求层次遍历二叉树，每层中最后一个节点

  • 层序遍历时，将节点与层数绑定为pair，压入队列时，将节点与层数同时压入队列，并记录每一层出现的最后一个节点

  • 层序遍历中，每一层的最后一个节点最后遍历到，随时更新对每层的最后一个节点即可

题目代码

/**
 * 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<int> rightSideView(TreeNode* root) {
        vector<int>view;
        queue<pair<TreeNode *,int> >Q;
        if(root){
            Q.push(make_pair(root,0));
        }
        while (!Q.empty()){
            TreeNode *nd=Q.front().first;
            int layer=Q.front().second;
            Q.pop();
            if(view.size()==layer){
                view.push_back(nd->val);
            } else{
                view[layer]=nd->val;
            }
            if(nd->left){
                Q.push(make_pair(nd->left,layer+1));
            }
            if(nd->right){
                Q.push(make_pair(nd->right,layer+1));
            }

        }
        return view;



    }
};

207. 课程表

力扣

  • n个课程m个依赖关系，看成顶点个数为n，边个数为m的有向图

  • 若为有向无环图，则可以完成课程

  • 否则不能

判断图是否有环

  • 深度优先遍历，如果正在遍历某一顶点（还未退出该顶点），又回到了该顶点，证明图有环

题目代码

struct node{
    int label;
    vector<node *>neighbors;//邻接表
    node(int x):label(x){};
};
class Solution {
public:
    //0 正在访问 -1没有访问 1访问过
    bool dfs(node *nd,vector<int>&vis){
        vis[nd->label]=0;
        for (int i = 0; i <nd->neighbors.size() ; ++i) {
            if(vis[nd->neighbors[i]->label]==-1){
                if(dfs(nd->neighbors[i],vis)==0){
                    return false;
                }
            }
            else if(vis[nd->neighbors[i]->label]==0){
                return false;
            }

        }
        vis[nd->label]=1;
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<node*>graph;
        vector<int>vis;
        for (int i = 0; i < numCourses; ++i){
            graph.push_back(new node(i));
            vis.push_back(-1);
        }
        for (int i = 0; i < prerequisites.size(); ++i){
            node *begin=graph[prerequisites[i][1]];
            node *end=graph[prerequisites[i][0]];
            begin->neighbors.push_back(end);
        }

        for (int i = 0; i < graph.size(); ++i){
            if(vis[i]==-1&&!dfs(graph[i],vis)){
                return false;
            }
        }
        return true;


    }
};

拓扑排序

宽度优先搜索，将入度为0的点添加至队列，完成一个顶点的搜索时，把它指向的所有顶点的入度都减一，若此时莫顶点入读为0则添加队列，完成宽度优先搜索后，所有点入度为0，则图无环，否则有环文章来源地址https://www.toymoban.com/news/detail-446227.html

题目代码

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<int> in;
        vector<vector<int> > graph;
        for (int i = 0; i < numCourses; ++i) {
            graph.push_back(vector<int>());
            in.push_back(0);
        }
        for (int i = 0; i < prerequisites.size(); ++i) {
            int end = prerequisites[i][0];
            int start = prerequisites[i][1];
            graph[start].push_back(end);
            in[end]++;
        }
        queue<int> Q;
        for (int i = 0; i < in.size(); ++i) {
            if (in[i] == 0) {
                Q.push(i);
            }
        }
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            for (int i = 0; i < graph[node].size(); ++i) {
                in[graph[node][i]]--;
                if (in[graph[node][i]] == 0) {
                    Q.push(graph[node][i]);
                }
            }

        }
        for (int i = 0; i < in.size(); ++i) {
            if (in[i]) {
                return false;
            }
        }
        return true;

    }
};

到了这里，关于二叉树与图（C++刷题笔记）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包