目錄

題目：

示例：

分析：

代碼：

題目：

示例：

分析：

題目給我們一棵二叉樹，讓我們返回站在二叉樹右邊從上到下看到的節(jié)點。

那實際上就是要我們對二叉樹進行層序遍歷，然后把每層的最右邊的一個節(jié)點拿出來。

所以問題實際上就是要我們對二叉樹進行層序遍歷，所以我們這邊介紹兩種層序遍歷的方法，分別是DFS和BFS，也就是深度優(yōu)先搜索和廣度優(yōu)先搜索。

首先是DFS深度優(yōu)先搜索，我們先定義一個空的二維數(shù)組，是用來存放層序遍歷的結(jié)果的。

我們對二叉樹進行先序遍歷，在遞歸遍歷的同時攜帶一個代表深度的參數(shù)。

如果存放結(jié)果的二維數(shù)組的size也就是里面一維數(shù)組的數(shù)量小于等于深度，那就是我們第一次碰到這一層的節(jié)點，我們就往二維數(shù)組的后面塞一個一維的空數(shù)組。

然后再根據(jù)深度來將當前節(jié)點的值塞到二維數(shù)組的某個一維數(shù)組里。

先序遍歷完畢，我們也就層序遍歷完畢了。

這是DFS層序遍歷的方法。我個人認為比較簡單，不過層序遍歷最經(jīng)典的是BFS廣度優(yōu)先搜索，所以這邊我們也將一下BFS怎么層序遍歷。

我們拿一個隊列，首先先把跟節(jié)點塞進隊列里。

然后進入一個while循環(huán)，只要隊列為空我們就退出循環(huán)，在循環(huán)體里我們先給存層序遍歷的二維列表里塞一個空的一維列表，然后先記錄一下隊列的長度，然后再for循環(huán)隊列長度次數(shù)，在for循環(huán)里再每次取出一個隊列里的節(jié)點，把節(jié)點的值塞進二維數(shù)組的最后一個一維數(shù)組里面。

再對節(jié)點做判斷，如果其左子樹不為空，就把左子節(jié)點塞進隊列里，如果其右子樹不為空，把右子節(jié)點再塞進去。

這樣就是每次我們只取二叉樹的一層節(jié)點，并且存住每層的節(jié)點值后，還把每個節(jié)點的子節(jié)點塞進了隊列，這樣隊列里就是下一層的節(jié)點了。

直到隊列為空，那么就表示層序遍歷完畢。

最終二維數(shù)組就是我們層序遍歷的結(jié)果。

以上兩種方法都可以對二叉樹進行層序遍歷。而本題中，我們需要把每層的最右邊的節(jié)點返回出去，所以我們還需要取走二維數(shù)組里每個數(shù)組的最后一個元素。

代碼：

DFS層序遍歷

class Solution {
public:
    vector<vector<int>>cache;
    void find(TreeNode* root,int deep){
        if(root==nullptr) return;
        if(cache.size()<=deep) cache.push_back(vector<int>(0));
        cache[deep].push_back(root->val);
        find(root->left,deep+1);
        find(root->right,deep+1);
    }
    vector<int> rightSideView(TreeNode* root) {
        find(root,0);
        vector<int>res;
        for(auto&c:cache){
            res.push_back(*(c.end()-1));
        }
        return res;
    }
};

BFS層序遍歷?文章來源地址http://www.zghlxwxcb.cn/news/detail-682985.html

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root==nullptr) return {};
        vector<vector<int>>cache;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            cache.push_back(vector<int>(0));
            int l=q.size();
            for(int i=0;i<l;i++){
                TreeNode* node=q.front();q.pop();
                cache.back().push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        vector<int>res;
        for(auto& c:cache){
            res.push_back(*(c.end()-1));
        }
        return res;
    }
};

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