专栏首页aCloudDeveloperLeetCode: 103_Binary Tree Zigzag Level Order Traversal | 二叉树Zigzag层次遍历 | Medium

LeetCode: 103_Binary Tree Zigzag Level Order Traversal | 二叉树Zigzag层次遍历 | Medium

本题也属于层次遍历的变形,不同之处在于其遍历的方法是交替进行的,形成一个ZigZag的曲线形式,如下:

代码如下:

 1 struct TreeNode {
 2     int            val;
 3     TreeNode*    left;
 4     TreeNode*    right;
 5     TreeNode(int x): val(x), left(NULL),right(NULL) {}
 6 };
 7 
 8 void Swap(vector<int> &ivec)
 9 {
10     int temp = 0;
11     int len = ivec.size();
12     for (int i = 0; i < len/2; i ++) {
13         temp = ivec.at(i);
14         ivec.at(i) = ivec.at(len-1-i);
15         ivec.at(len-1-i) = temp;
16     }
17 }
18 
19 vector<vector <int> > zigzagLevelOrder(TreeNode *root)
20 {
21     vector<vector<int> > tree_vector;
22     vector<int> ivec;
23     queue<TreeNode *> tree_queue;
24     if (NULL == root)
25         return tree_vector;
26 
27     tree_queue.push(root);
28     tree_queue.push(NULL);
29     int nLevelCount = 1;
30     while (true) {
31         TreeNode *pTemp = tree_queue.front();
32         tree_queue.pop();
33         if (pTemp == NULL) {
34             if (nLevelCount%2 == 0) { //if the num of level is odd, swap the ivec;
35                 Swap(ivec);
36             }
37             tree_vector.push_back(ivec);
38             ivec.clear();
39             if (tree_queue.empty())
40                 break;
41             tree_queue.push(NULL);
42             nLevelCount ++;
43         }
44         else {
45             ivec.push_back(pTemp->val);
46             if (pTemp->left)
47                 tree_queue.push(pTemp->left);
48             if (pTemp->right)
49                 tree_queue.push(pTemp->right);
50         }
51     }
52     return tree_vector;
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode:4_Median of Two Sorted Arrays | 求两个排序数组的中位数 | Hard

    题目: There are two sorted arrays nums1 and nums2 of size m and n respectively. F...

    CloudDeveloper
  • LeetCode:1_Two_Sum | 两个元素相加等于目标元素 | Medium

    题目: Given an array of integers, find two numbers such that they add up to a spec...

    CloudDeveloper
  • LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium

    题目: Given a string, find the length of the longest substring without repeating c...

    CloudDeveloper
  • 0661-6.2.0-Hadoop数据备份与恢复

    在Hadoop集群中,数据文件是以Block的方式存储在HDFS上,而HDFS上数据的名称,副本存储的地址等都是通过NameNode上的元数据来保存的。Hive...

    Fayson
  • 实验楼课程管理程序-深入学习《C++ Primer第五版》实验报告&学习笔记1

    本片博客为实验楼的训练营课程深入学习《C++ Primer第五版》的实验报告和学习笔记。

    用户7043923
  • log4j2 与 spring mvc整合

    log4j2不仅仅是log4j的简单升级,而是整个项目的重构,官网地址:http://logging.apache.org/log4j/2.x/,大家可以从官网...

    菩提树下的杨过
  • 自定义Spring Boot Starter

    十毛
  • Task和backStack(本篇章核心)

    对Task和backStack的认识过程 1.由demo测试得到的关系图: ? 1.一个task中可以有多个app的Activity, 由于一个app可以对应...

    梦里茶
  • C#中关于SqlDataAdapter的Update(dataTable)方法

    C#用来更新数据库的方式有两种(暂时我知道两种)一种就是sql语句的update,第二种就是我接下来要说的SqlDataAdapter的Update()方法。

    提莫队长
  • LeetCode 904. 水果成篮(滑动窗口)

    在一排树中,第 i 棵树产生 tree[i] 型的水果。 你可以从你选择的任何树开始,然后重复执行以下步骤:

    Michael阿明

扫码关注云+社区

领取腾讯云代金券