一、層序遍歷

? 層序遍歷，是按照層數(shù)從低到高，同一層從左到右遍歷。在這里采用遞歸法是無法做到的，觀察遍歷的特點(diǎn)，這里需再加一個(gè)隊(duì)列來實(shí)現(xiàn)。

天津網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

? 在將一層一層的二叉樹節(jié)點(diǎn)放入隊(duì)列以及彈出隊(duì)列的操作中，需要記錄和知道彈出的個(gè)數(shù)size。

具體思路和步驟如代碼：

102.二叉樹的層序遍歷?#力扣題目鏈接

class Solution {
public:
    vector>levelOrder(TreeNode* root) {
        queueque;
        vector>result; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            vectorvec;                    //記錄某一層的結(jié)果
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點(diǎn)
                que.pop();                      //隊(duì)列彈出
                vec.push_back(node->val);       //將彈出的節(jié)點(diǎn)數(shù)值放入數(shù)組中
                if(node->left) que.push(node->left);   //獲取這個(gè)節(jié)點(diǎn)的左孩子
                if(node->right) que.push(node->right); //獲取這個(gè)節(jié)點(diǎn)的右孩子
            }
            result.push_back(vec);              //將一層的數(shù)組放入到結(jié)果中
        }
        return result;
    }
};

107.二叉樹的層序遍歷②#力扣題目鏈接

在102的基礎(chǔ)上進(jìn)行結(jié)果翻轉(zhuǎn)即可。

reverse(result.begin(), result.end());

199.二叉樹的右視圖#力扣題目鏈接

? 這道題的核心思想：就是將每一層彈出的最后一個(gè)放入結(jié)果數(shù)組中，就可以了。

class Solution {
public:
    vectorrightSideView(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點(diǎn)
                que.pop();                      //隊(duì)列彈出
                if(size == 0){
                    result.push_back(node->val);       //最后一個(gè)彈出的放入結(jié)果數(shù)組即可
                }
                if(node->left) que.push(node->left);   //獲取這個(gè)節(jié)點(diǎn)的左孩子
                if(node->right) que.push(node->right); //獲取這個(gè)節(jié)點(diǎn)的右孩子
            }
        }
        return result;
    }
};

637.二叉樹的層平均值?#力扣題目鏈接

? 這一道題的思路：在每一層的元素彈出時(shí)，記錄下來并進(jìn)行加和，在每一層彈出結(jié)束后將再將平均數(shù)放到result數(shù)組中即可。

class Solution {
public:
    vectoraverageOfLevels(TreeNode* root) {
        double sum = 0;    //記錄求和
        vectorresult;
        queueque;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            double count = 0;               //記錄某一層的元素個(gè)數(shù)
            double sum = 0;                 //記錄所有數(shù)的加和
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                count++;
                sum += node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
        }
            result.push_back(sum / count);  //將每一層的平均數(shù)放到數(shù)組里
        }
        return result;
    }
};

429.N叉樹的層序遍歷#力扣題目鏈接

? n叉樹和二叉樹的層序遍歷區(qū)別不大，這里將left、right變換成children[i]就可以了。

class Solution {
public:
    vector>levelOrder(Node* root) {
        queueque;
        vector>result; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            vectorvec;                    //記錄某一層的結(jié)果
            while(size--){
                Node* node = que.front();  //獲取要彈出的節(jié)點(diǎn)
                que.pop();                      //隊(duì)列彈出
                vec.push_back(node->val);       //將彈出的節(jié)點(diǎn)數(shù)值放入數(shù)組中
                for(int i = 0; i< node->children.size(); i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);              //將一層的數(shù)組放入到結(jié)果中
        }
        return result;
    }
};

515.在每個(gè)樹行中找大值?#力扣題目鏈接

? 這道題，在每層進(jìn)行比較即可獲得大值即可。

class Solution {
public:
    vectorlargestValues(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            int max = INT32_MIN;                        //記錄大值
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點(diǎn)
                que.pop();                      //隊(duì)列彈出
                if(node->val >max){                    //進(jìn)行數(shù)值的比較，獲得大值
                    max = node->val;
                }
                if(node->left) que.push(node->left);   //獲取這個(gè)節(jié)點(diǎn)的左孩子
                if(node->right) que.push(node->right); //獲取這個(gè)節(jié)點(diǎn)的右孩子
            }
            result.push_back(max);   
        }
        return result;
    }
};

116.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針#力扣題目鏈接

? 這里類似于鏈表操作，記錄好上一個(gè)元素nodePre即可，之后將next指針指向下一個(gè)元素即可。

class Solution {
public:
    Node* connect(Node* root) {
        queueque;
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            Node* nodePre;
            Node* node;
            for(int i = 0; inext = node;
                    nodePre = nodePre->next;
                }
                if(node->left) que.push(node->left);   //獲取這個(gè)節(jié)點(diǎn)的左孩子
                if(node->right) que.push(node->right); //獲取這個(gè)節(jié)點(diǎn)的右孩子
            }
            nodePre->next = NULL;
        }
        return root;
    }
};

117.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針2#力扣題目鏈接

解題邏輯和116一模一樣。

104.二叉樹的大深度#力扣題目鏈接

? 在遍歷的同時(shí)，記錄層數(shù)即可。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queueque;
        int result = 0;                          //記錄層數(shù)
        if(root != NULL)  que.push(root);        //彈入根節(jié)點(diǎn)
        while(!que.empty()){
            int size = que.size();              //記錄size個(gè)數(shù)
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點(diǎn)
                que.pop();                      //隊(duì)列彈出
                if(node->left) que.push(node->left);   //獲取這個(gè)節(jié)點(diǎn)的左孩子
                if(node->right) que.push(node->right); //獲取這個(gè)節(jié)點(diǎn)的右孩子
            }
            result++;
        }
        return result;
    }
};

111.二叉樹的最小深度#力扣題目鏈接

? 判斷條件：當(dāng)左右孩子為空時(shí)，說明到遍歷的最低點(diǎn)了。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int result = 0;
        queueque;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            result++; // 記錄最小深度
            for (int i = 0; i< size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 當(dāng)左右孩子都為空的時(shí)候
                    return result;
                }
            }
        }
        return result;
    }
};

二、翻轉(zhuǎn)二叉樹

題目：#力扣題目鏈接

給你一棵二叉樹的根節(jié)點(diǎn)?root，翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點(diǎn)。

這道題解決的方法，先需要確定遍歷方式，采用前序和后序遍歷方式比較好，這里只需要進(jìn)行左右孩子的交換即可。

class Solution {
public:
    void traversal(TreeNode *cur, vector& dep){           //前序遍歷
        if(cur == NULL) return;
        dep.push_back(cur->val);        //中
        swap(cur->left, cur->right);                //交換左右孩子
        traversal(cur->left, dep);      //左
        traversal(cur->right, dep);     //右
    }
    TreeNode* invertTree(TreeNode* root) {
        vectorresult;
        traversal(root, result);            
        return root;
    }
};

三、對(duì)稱二叉樹

題目：#力扣題目鏈接

給你一個(gè)二叉樹的根節(jié)點(diǎn)?root， 檢查它是否軸對(duì)稱。

? 這道題判斷是二叉樹是否為對(duì)稱二叉樹，即左右孩子是否可以翻轉(zhuǎn)不變，體現(xiàn)在外側(cè)節(jié)點(diǎn)和內(nèi)側(cè)節(jié)點(diǎn)是否相等。

? 所以需要不停的判斷左右孩子的信息，之后返回到根節(jié)點(diǎn)，這里采用遍歷方式就應(yīng)該只能采取后序遍歷。

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        //這里判斷條件需要理解透徹，容易出錯(cuò)
        if(left == NULL && right != NULL) return false;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right == NULL) return true;
        else if(left->val != right->val) return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool result = outside && inside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left, root->right);
    }
};

四、總結(jié)和收獲

? 在這一章節(jié)，需要我們?nèi)チ私舛鏄鋷追N遍歷方式的特點(diǎn)，并在實(shí)現(xiàn)過程中有意識(shí)的去分析采用那種遍歷方式。?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：代碼隨想錄第15天：二叉樹-創(chuàng)新互聯(lián)
文章起源：http://chinadenli.net/article40/deehho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、域名注冊(cè)、搜索引擎優(yōu)化、定制開發(fā)、網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)