图解LeetCode第 103 号问题：二叉树的锯齿形层次遍历

该文已加入开源项目：LeetCodeAnimation（用动画的形式呈现解LeetCode题目的思路，目前 5000 Star ）。地址：https://github.com/MisterBooo/LeetCodeAnimation

LeetCode上第103 号问题：二叉树的锯齿形层次遍历

题目描述

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

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

返回其层次遍历结果：

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

思路解析

该问题需要用到队列，与之前的二叉树的层次遍历类似，不同点在于在偶数层需要翻转一下。

• 建立一个queue

• 先把根节点放进去，这时候找根节点的左右两个子节点

• 去掉根节点，此时queue里的元素就是下一层的所有节点

• 循环遍历，将结果存到一个一维向量里

• 遍历完之后再把这个一维向量存到二维向量里

• 如果该层为偶数层，则reverse翻转一下

• 以此类推，可以完成层序遍历

动画演示

动画演示GIF加载有点慢，请稍等片刻^_^

参考代码

 1class Solution{
 2public:
 3    vector<vector<int>> zigzagLevelOrder(TreeNode* root){
 4        vector<vector<int>> res2D;
 5        if (!root) return res2D;
 6        queue<TreeNode*> q;
 7        q.push(root);
 8        int level=1;
 9        int count=1;
10        int countTmp=0;
11        while(!q.empty()){
12                countTmp=0;
13                vector<int> res1D;
14                while (count>0){
15                    res1D.push_back(q.front()->val);
16                    if (q.front()->left) {q.push(q.front()->left);countTmp++;}
17                    if (q.front()->right) {q.push(q.front()->right);countTmp++;}
18                    q.pop();
19                    count--;
20                }
21                if (level%2==0) reverse(res1D.begin(),res1D.end());   
22                count=countTmp;
23                res2D.push_back(res1D);
24                level++;               
25        }
26        return res2D;
27    }
28};

代码截图