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

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

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

题目描述

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

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

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

返回其层次遍历结果:

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

思路解析

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

  • 建立一个queue

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

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

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

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

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

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

动画演示

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

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

参考代码

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

代码截图

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


End

关于本号

作者程序员小吴,哈工大学渣,目前正在学算法,开源项目  LeetCodeAnimation 」5000star,GitHub Trending 榜 连续半个月登顶欢迎大家关注我的微信公众号:五分钟学算法,一起学习,一起进步!

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


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解LeetCode第 103 号问题:二叉树的锯齿形层次遍历

我还会在以下平台发布内容

GitHub 哔哩哔哩