精选力扣500题第10题 LeetCode 103. 二叉树的锯齿形层序遍历【c++详细题解】

向右看齐 2021-07-24 11:06 283阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：  
给定二叉树 \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

返回锯齿形层序遍历如下：

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

### 2、思路 ###

**(BFS)**  O ( n ) O(n) O(n)  
我们从根节点开始按宽度优先的顺序遍历整棵树，每次先扩展左儿子，再扩展右儿子。

这样我们会：

1.  先扩展根节点；
2.  再依次扩展根节点的左右儿子，也就是从左到右扩展第二层节点；
3.  再依次从左到右扩展第三层节点；
4.  依次类推

然后在遍历过程中我们给每一层加一个结尾标记`NULL`,当我们访问到一层的结尾时，由于`BFS`的特点，我们刚好把下一层都加到了队列中。这个时候就可以给这层加上结尾标记`NULL`了。

再给每一层加一个标记，奇数行为从左到右，偶数行为从右到左。

### 3、代码 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<vector<int>> printFromTopToBottom(TreeNode* root) { 
            vector<vector<int>>res;
            if(!root) return res;
            queue<TreeNode*>q;
            vector<int>level; //记录一层的节点
            q.push(root);
            q.push(NULL);// 一层的结尾标记
            bool flag = false;
            while(q.size())
            { 
                auto t = q.front();
                q.pop();
                if(!t)
                { 
                    if(!level.size()) break; //避免陷入死循环
                    if(flag) reverse(level.begin(),level.end());
                    res.push_back(level);
                    level.clear();
                    q.push(NULL);
                    flag = !flag;
                }
                else
                { 
                    level.push_back(t->val);
                    if(t->left) q.push(t->left);
                    if(t->right) q.push(t->right);
                }
            }
            return res;
        }
    };

**原题链接：**[103. 二叉树的锯齿形层序遍历][103.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[103.]: https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/8b368e8007284ec68376fa37291a74ec.png