二叉樹與圖（C++刷題筆記）

113.?路徑總和 II

力扣

• 從根節(jié)點深度遍歷二叉樹，先序遍歷時，將節(jié)點存儲至path棧中，使用path_val累加節(jié)點值

• 當(dāng)遍歷到葉子節(jié)點，檢查path_val是否為sum，若是，則將pathpush進(jìn)入res的結(jié)果中去

• 在后續(xù)變量，將該節(jié)點從path棧中彈出，path_val減去節(jié)點值

題目代碼

/**
 * 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.?二叉樹的最近公共祖先

力扣

• 兩個節(jié)點公共祖先一定從根節(jié)點，至這兩個節(jié)點的路徑上

• 由于求公共祖先中的最近公共祖先，那么即同時出現(xiàn)在這兩條路徑上的里根幾點最遠(yuǎn)的節(jié)點

• 求兩個節(jié)點路徑最后一個相同的節(jié)點

求根節(jié)點到某一個節(jié)點的路徑

• 從根節(jié)點遍歷至該節(jié)點，找到節(jié)點后就結(jié)束搜索

• 將遍歷過程中遇到的節(jié)點按順序存儲，節(jié)點即路徑

  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();
    }

求兩路徑下最后一個相同節(jié)點

• 求出較短路徑長度n

• 同時遍歷p節(jié)點與q節(jié)點路徑，遍歷n個節(jié)點，最后一個相同的節(jié)點即最近公共祖先

題目代碼

/**
 * 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進(jìn)入vector，順序遍歷vector中節(jié)點，鏈接相鄰兩節(jié)點

/**
 * 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.?二叉樹的右視圖

• 從二叉樹的右側(cè)觀察它，將觀察到的節(jié)點從上到下順序輸出，就是求層次遍歷二叉樹，每層中最后一個節(jié)點

• 層序遍歷時，將節(jié)點與層數(shù)綁定為pair，壓入隊列時，將節(jié)點與層數(shù)同時壓入隊列，并記錄每一層出現(xiàn)的最后一個節(jié)點

• 層序遍歷中，每一層的最后一個節(jié)點最后遍歷到，隨時更新對每層的最后一個節(jié)點即可

題目代碼

/**
 * 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個依賴關(guān)系，看成頂點個數(shù)為n，邊個數(shù)為m的有向圖

• 若為有向無環(huán)圖，則可以完成課程

• 否則不能

判斷圖是否有環(huán)

• 深度優(yōu)先遍歷，如果正在遍歷某一頂點（還未退出該頂點），又回到了該頂點，證明圖有環(huán)

題目代碼

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;


    }
};

拓?fù)渑判?/h4>

寬度優(yōu)先搜索，將入度為0的點添加至隊列，完成一個頂點的搜索時，把它指向的所有頂點的入度都減一，若此時莫頂點入讀為0則添加隊列，完成寬度優(yōu)先搜索后，所有點入度為0，則圖無環(huán)，否則有環(huán)文章來源地址http://www.zghlxwxcb.cn/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;

    }
};

到了這里，關(guān)于二叉樹與圖（C++刷題筆記）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！