代碼隨想錄第15天：二叉樹-創(chuàng)新互聯

一、層序遍歷

? 層序遍歷，是按照層數從低到高，同一層從左到右遍歷。在這里采用遞歸法是無法做到的，觀察遍歷的特點，這里需再加一個隊列來實現。

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

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

具體思路和步驟如代碼：

102.二叉樹的層序遍歷?#力扣題目鏈接
class Solution {
public:
    vector>levelOrder(TreeNode* root) {
        queueque;
        vector>result; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            vectorvec;                    //記錄某一層的結果
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點
                que.pop();                      //隊列彈出
                vec.push_back(node->val);       //將彈出的節(jié)點數值放入數組中
                if(node->left) que.push(node->left);   //獲取這個節(jié)點的左孩子
                if(node->right) que.push(node->right); //獲取這個節(jié)點的右孩子
            }
            result.push_back(vec);              //將一層的數組放入到結果中
        }
        return result;
    }
};
107.二叉樹的層序遍歷②#力扣題目鏈接

在102的基礎上進行結果翻轉即可。

reverse(result.begin(), result.end());
199.二叉樹的右視圖#力扣題目鏈接

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

class Solution {
public:
    vectorrightSideView(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點
                que.pop();                      //隊列彈出
                if(size == 0){
                    result.push_back(node->val);       //最后一個彈出的放入結果數組即可
                }
                if(node->left) que.push(node->left);   //獲取這個節(jié)點的左孩子
                if(node->right) que.push(node->right); //獲取這個節(jié)點的右孩子
            }
        }
        return result;
    }
};
637.二叉樹的層平均值?#力扣題目鏈接

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

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;               //記錄某一層的元素個數
            double sum = 0;                 //記錄所有數的加和
            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);  //將每一層的平均數放到數組里
        }
        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é)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            vectorvec;                    //記錄某一層的結果
            while(size--){
                Node* node = que.front();  //獲取要彈出的節(jié)點
                que.pop();                      //隊列彈出
                vec.push_back(node->val);       //將彈出的節(jié)點數值放入數組中
                for(int i = 0; i< node->children.size(); i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);              //將一層的數組放入到結果中
        }
        return result;
    }
};
515.在每個樹行中找大值?#力扣題目鏈接

? 這道題，在每層進行比較即可獲得大值即可。

class Solution {
public:
    vectorlargestValues(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //彈入根節(jié)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            int max = INT32_MIN;                        //記錄大值
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點
                que.pop();                      //隊列彈出
                if(node->val >max){                    //進行數值的比較，獲得大值
                    max = node->val;
                }
                if(node->left) que.push(node->left);   //獲取這個節(jié)點的左孩子
                if(node->right) que.push(node->right); //獲取這個節(jié)點的右孩子
            }
            result.push_back(max);   
        }
        return result;
    }
};
116.填充每個節(jié)點的下一個右側節(jié)點指針#力扣題目鏈接

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

class Solution {
public:
    Node* connect(Node* root) {
        queueque;
        if(root != NULL)  que.push(root);        //彈入根節(jié)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            Node* nodePre;
            Node* node;
            for(int i = 0; inext = node;
                    nodePre = nodePre->next;
                }
                if(node->left) que.push(node->left);   //獲取這個節(jié)點的左孩子
                if(node->right) que.push(node->right); //獲取這個節(jié)點的右孩子
            }
            nodePre->next = NULL;
        }
        return root;
    }
};
117.填充每個節(jié)點的下一個右側節(jié)點指針2#力扣題目鏈接

解題邏輯和116一模一樣。

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

? 在遍歷的同時，記錄層數即可。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queueque;
        int result = 0;                          //記錄層數
        if(root != NULL)  que.push(root);        //彈入根節(jié)點
        while(!que.empty()){
            int size = que.size();              //記錄size個數
            while(size--){
                TreeNode* node = que.front();  //獲取要彈出的節(jié)點
                que.pop();                      //隊列彈出
                if(node->left) que.push(node->left);   //獲取這個節(jié)點的左孩子
                if(node->right) que.push(node->right); //獲取這個節(jié)點的右孩子
            }
            result++;
        }
        return result;
    }
};
111.二叉樹的最小深度#力扣題目鏈接

? 判斷條件：當左右孩子為空時，說明到遍歷的最低點了。

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) { // 當左右孩子都為空的時候
                    return result;
                }
            }
        }
        return result;
    }
};
二、翻轉二叉樹

題目：#力扣題目鏈接

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

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

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;
    }
};
三、對稱二叉樹

題目：#力扣題目鏈接

給你一個二叉樹的根節(jié)點?root， 檢查它是否軸對稱。

? 這道題判斷是二叉樹是否為對稱二叉樹，即左右孩子是否可以翻轉不變，體現在外側節(jié)點和內側節(jié)點是否相等。

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

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        //這里判斷條件需要理解透徹，容易出錯
        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é)，需要我們去了解二叉樹幾種遍歷方式的特點，并在實現過程中有意識的去分析采用那種遍歷方式。?

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

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

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

廣告

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

外貿網站建設