快捷導航

C++實現(xiàn)LeetCode(103.二叉樹的之字形層序遍歷)

更新時間：2021年07月21日 15:29:32 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(103.二叉樹的之字形層序遍歷),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉樹的之字形層序遍歷

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 來統(tǒng)計當前的層數(shù)（從0開始），將所有的奇數(shù)層的結(jié)點值進行翻轉(zhuǎn)一下即可，參見代碼如下：

解法一：

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

我們可以將上面的解法進行優(yōu)化一下，翻轉(zhuǎn)數(shù)組雖然可行，但是比較耗時，假如能夠直接計算出每個結(jié)點值在數(shù)組中的坐標，就可以直接進行更新了。由于每層的結(jié)點數(shù)是知道的，就是隊列的元素個數(shù)，所以可以直接初始化數(shù)組的大小。此時使用一個變量 leftToRight 來標記順序，初始時是 true，當此變量為 true 的時候，每次加入數(shù)組的位置就是i本身，若變量為 false 了，則加入到 size-1-i 位置上，這樣就直接相當于翻轉(zhuǎn)了數(shù)組。每層遍歷完了之后，需要翻轉(zhuǎn) leftToRight 變量，同時不要忘了將 oneLevel 加入結(jié)果 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;
    }
};

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

到此這篇關(guān)于C++實現(xiàn)LeetCode(103.二叉樹的之字形層序遍歷)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)二叉樹的之字形層序遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: