亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

用C++實現二叉樹的之字形層序遍歷

發布時間:2021-07-21 16:41:25 來源:億速云 閱讀:217 作者:chen 欄目:開發技術

這篇文章主要介紹“用C++實現二叉樹的之字形層序遍歷”,在日常操作中,相信很多人在用C++實現二叉樹的之字形層序遍歷問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”用C++實現二叉樹的之字形層序遍歷”的疑惑有所幫助!接下來,請跟著小編一起來學習吧!

二叉樹的之字形層序遍歷

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7

return its zigzag level order traversal as:

[
[3],
[20,9],
[15,7]
]

這道二叉樹的之字形層序遍歷是之前那道 Binary Tree Level Order Traversal 的變形,不同之處在于一行是從左到右遍歷,下一行是從右往左遍歷,交叉往返的之字形的層序遍歷。最簡單直接的方法就是利用層序遍歷,并使用一個變量 cnt 來統計當前的層數(從0開始),將所有的奇數層的結點值進行翻轉一下即可,參見代碼如下:

解法一:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        int cnt = 0;
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            if (cnt % 2 == 1) reverse(oneLevel.begin(), oneLevel.end());
            res.push_back(oneLevel);
            ++cnt;
        }
        return res;
    }
};

我們可以將上面的解法進行優化一下,翻轉數組雖然可行,但是比較耗時,假如能夠直接計算出每個結點值在數組中的坐標,就可以直接進行更新了。由于每層的結點數是知道的,就是隊列的元素個數,所以可以直接初始化數組的大小。此時使用一個變量 leftToRight 來標記順序,初始時是 true,當此變量為 true 的時候,每次加入數組的位置就是i本身,若變量為 false 了,則加入到 size-1-i 位置上,這樣就直接相當于翻轉了數組。每層遍歷完了之后,需要翻轉 leftToRight 變量,同時不要忘了將 oneLevel 加入結果 res,參見代碼如下:

解法二:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        bool leftToRight = true;
        while (!q.empty()) {
            int size = q.size();
            vector<int> oneLevel(size);
            for (int i = 0; i < size; ++i) {
                TreeNode *t = q.front(); q.pop();
                int idx = leftToRight ? i : (size - 1 - i);
                oneLevel[idx] = t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            leftToRight = !leftToRight;
            res.push_back(oneLevel);
        }
        return res;
    }
};

我們也可以使用遞歸的方法來解,這里實際上用的是先序遍歷,遞歸函數需要一個變量 level 來記錄當前的深度,由于 level 是從0開始的,假如結果 res 的大小等于 level,就需要在結果 res 中新加一個空集,這樣可以保證 res[level] 不會越界。取出 res[level] 之后,判斷 levle 的奇偶,若其為偶數,則將 node->val 加入 oneLevel 的末尾,若為奇數,則加在 oneLevel 的開頭。然后分別對 node 的左右子結點調用遞歸函數,此時要傳入 level+1 即可,參見代碼如下:

解法三:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        helper(root, 0, res);
        return res;
    }
    void helper(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() <= level) {
            res.push_back({});
        }
        vector<int> &oneLevel = res[level];
        if (level % 2 == 0) oneLevel.push_back(node->val);
        else oneLevel.insert(oneLevel.begin(), node->val);
        helper(node->left, level + 1, res);
        helper(node->right, level + 1, res);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/103

類似題目:

Binary Tree Level Order Traversal

參考資料:

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33815/My-accepted-JAVA-solution

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33825/c%2B%2B-5ms-version%3A-one-queue-and-without-reverse-operation-by-using-size-of-each-level

到此,關于“用C++實現二叉樹的之字形層序遍歷”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注億速云網站,小編會繼續努力為大家帶來更多實用的文章!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

c++
AI

汕头市| 翁牛特旗| 应用必备| 昌乐县| 大石桥市| 宽甸| 东乡族自治县| 巩留县| 丰原市| 武威市| 盐边县| 青州市| 天镇县| 榆中县| 太和县| 南宫市| 东阳市| 阜康市| 朝阳区| 河西区| 宿州市| 太谷县| 洪洞县| 怀仁县| 财经| 龙胜| 盐亭县| 内黄县| 库伦旗| 唐山市| 大关县| 诸城市| 休宁县| 平凉市| 闸北区| 偏关县| 新丰县| 论坛| 泉州市| 焉耆| 苍山县|