Day122 | 灵神 | 二叉树 | 二叉树的层序遍历 二叉树的锯齿状遍历

102.二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

思路：

笔者写过很多次了这里不再赘述，初学者可以看灵神视频二叉树的层序遍历【基础算法精讲 13】_哔哩哔哩_bilibili

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if(root==nullptr)
            return res;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int> path;
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                path.push_back(t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            res.push_back(path);
        }
        return res;
    }
};

103.二叉树的锯齿状遍历

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

思路：

和层序遍历区别就是加一个计数器，如果是奇数层就翻转一下再往答案里面放

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        int count=0;
        queue<TreeNode *> q;
        if(root==nullptr)
            return res;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            vector<int> path;
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                path.push_back(t->val);
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            /*这是灵神的做法，是等价的
            if (res.size() % 2) ranges::reverse(path);
            */
            if(count%2==1)
                ranges::reverse(path);
            count++;
            res.push_back(path);
        }
        return res;
    }
};