首页 > 代码库 > 【LeetCode】Binary Tree Zigzag Level Order Traversal
【LeetCode】Binary Tree Zigzag Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
层次遍历，每一层加入一个vector<int> cur
当遍历到新一层时，将cur加入result，并清空，准备记录新一层数据。
以root为第0层，则奇数层的cur在加入result之前要reverse，变为从右往左。
以上描述涉及两个问题：
1、怎么知道当前在第几层？
2、怎么知道当前进入了新层？
解决：
1、为了判断遍历到的层数，设置一个Node结构，里面存放level。level从0起计数。
第i层的节点将子女进队列时，层数设为i+1。
2、设置一个变量lastLevel，记录上一个pop出来节点的层数。
如果当前pop出来节点的层数为lastLevel+1，即为到了新的层次。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */struct Node{ TreeNode* tree; int level;//level%2==0 ——> left to right; level%2==1 --> right to left Node(TreeNode* root, int l): tree(root), level(l) {}};class Solution {public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > result; if(root == NULL) return result; queue<Node*> q; vector<int> cur; Node* rootNode = new Node(root, 0); int lastLevel = 0; //if current level is bigger than lastLevel, means new level q.push(rootNode); while(!q.empty()) { Node* front = q.front(); q.pop(); if(front->level > lastLevel) {//new level if(lastLevel%2 == 1) reverse(cur.begin(), cur.end()); result.push_back(cur); cur.clear(); lastLevel = front->level; } cur.push_back(front->tree->val); if(front->tree->left) { Node* leftNode = new Node(front->tree->left, front->level+1); q.push(leftNode); } if(front->tree->right) { Node* rightNode = new Node(front->tree->right, front->level+1); q.push(rightNode); } } //add last level if(lastLevel%2 == 1) reverse(cur.begin(), cur.end()); result.push_back(cur); return result; }};
【LeetCode】Binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。