BinaryTreeZigzagLevelOrderTraversal [source code]
public class BinaryTreeZigzagLevelOrderTraversal {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res_lss = new ArrayList<> ();
if (root == null)
return res_lss;
Deque<TreeNode> deque = new ArrayDeque<> ();
deque.offer (root);
int level = 0;
while (!deque.isEmpty ()) {
int size = deque.size ();
List<Integer> ls = new ArrayList<> ();
Deque<TreeNode> next_deque = new ArrayDeque<> ();
boolean go_right = level++ % 2 == 0;
for (int i = 0; i < size; i++) {
TreeNode cur = go_right ? deque.pollFirst () : deque.pollLast ();
ls.add (cur.val);
if (go_right) {
if (cur.left != null) next_deque.offer (cur.left);
if (cur.right != null) next_deque.offer (cur.right);
} else {
if (cur.right != null) next_deque.offerFirst (cur.right);
if (cur.left != null) next_deque.offerFirst (cur.left);
}
}
deque = next_deque;
res_lss.add (ls);
}
return res_lss;
}
}
/******************************************************************************/
public static void main(String[] args) {
BinaryTreeZigzagLevelOrderTraversal.Solution tester = new BinaryTreeZigzagLevelOrderTraversal.Solution();
}
}
自己之前尝试写LeetCode风格的BST serialize的时候, 就感觉这个Null不好处理, 所以如果这题实际上是面试的时候出现, 最好是要问清楚多几个例子; 哦不对, 你输出的结果根本不需要包含Null;
这个题目很直观的一个感觉就是用BFS, 毕竟是一个一个level一个level的操作;
最后硬是超时了才做出来了, 速度是3ms (5%). 看起来很简单的一个题目, 吭哧吭哧这么半天, 真的丢人;
这个问题在解决的时候一个关键的思路就是, 在这个变动当中要保持一个不变量: 也就是当你往next里面丢的时候, 始终是一个从左到右的顺序丢, 或者说保证每一个level在刚刚被放到Deque里面结束的时候, 全都是正常的head to last: left to right的顺序; 有这个参照, 写代码的时候才不要频繁的考虑到底我现在处理的这个level本身存放的顺序是什么样的;
然后就是代码逻辑自己小心一点就行了, offer的位置需要考虑, 然后left和right谁先处理, 这个顺序也要考虑; 我一开始没有意识到这一点, 写了这个错误代码:
if (cur.left != null) {
if (go_right) next_deque.offerLast (cur.left);
else next_deque.offerFirst (cur.left);
}
if (cur.right != null) {
if (go_right) next_deque.offerLast (cur.right);
else next_deque.offerFirst (cur.right);
}
这个完全是固化的;
另外, 这题一个小的技巧: BFS的时候, queue里面实际上始终只要维护一个level就行了, 所以我这里写法上面, 是直接两个level交替着更新; 这个还是不难想到的; 如果不使用这个方法, 这题可能会出问题, 因为我们会有pollLast和pollFast同时发生, 那么你最后怎么处理?
当然, 我后来想了一下, 实际上还是可以不用next来完成的, 比如你从last开始Poll的时候(从右到左), 那么你就从first offer, 反之亦然; 不过这个最后还是依赖一个iteration只处理一个level这个性质, 所以其实也没差;
没有editorial;
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level)
{
if(curr == null) return;
if(sol.size() <= level)
{
List<Integer> newLevel = new LinkedList<>();
sol.add(newLevel);
}
List<Integer> collection = sol.get(level);
if(level % 2 == 0) collection.add(curr.val);
else collection.add(0, curr.val);
travel(curr.left, sol, level + 1);
travel(curr.right, sol, level + 1);
}
}
O(n) solution by using LinkedList along with ArrayList. So insertion in the inner list and outer list are both O(1),
Using DFS and creating new lists when needed.
should be quite straightforward. any better answer?
DFS做一个level处理的问题其实之前也见到过了, 虽然麻烦一点, 但是能写; 一个重要的依赖的技巧就是判断res里面对应当前level的list是否已经存在: 这个是依赖于分析DFS本身的order;
基本就是一个只考虑当前node的做法(当然, 得知道对应的level, 这个不难), 然后想好从哪个位置add就行了; 另外, 他这个add, 一会儿从头, 一会儿从尾巴, 所以不可能始终是O(1)的; 这个跟你用什么list没有关系;
这个图上面好像没有标注出来; 不过ArrayList add at 0是O(N), LinkedList是1, 这个应该还是很好理解的; 虽然要记得LinkedList实际上默认的add就是从head开始add的, 所以上面的表说是O(1)的add;
here is my accepted Java code. Just a little change from the Binary Tree Level Order Traversal
I use a queue to implement BFS. Each time when I poll a node, I add this node value to level. I use a variable zigzag to indicate whether add from left to right or right to left. If zigzag == false, it is from left to right; if zigzag == true, it is from right to left.
And from right to left just need to use ArrayList.add(0, value) method
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean zigzag = false;
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int cnt = queue.size();
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
if (zigzag) {
level.add(0, node.val);
}
else {
level.add(node.val);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(level);
zigzag = !zigzag;
}
return res;
@marcusgao I like your zigzag variable. Very readable! Here is a shorter version.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
if (root != null) q.offer(root);
List<List<Integer>> ret = new ArrayList<>();
for (boolean zigzag = false; !q.isEmpty(); zigzag = !zigzag) {
List<Integer> level = new LinkedList<>();
for (int size = q.size(); size > 0; size--) {
TreeNode n = q.poll();
level.add((zigzag ? 0 : level.size()), n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
ret.add(level);
}
return ret;
}
这个看起来倒是非常的简练;
他们的做法之所以能够这么简洁, 是因为他们其实是没有改变BFS本身的queue的操作方式, 他们的操作全都集中在最后结果list的操作方式; 这个虽然可能会损失一点速度, 但是集中了复杂度, 让整个算法的结构和设计简单很多; 比如, 他这个思路就完全不用考虑left和right谁先add, 无所谓的: 你的queue操作完全就是照着平常BFS的方式来就行了;
不要这么排斥add at index这个操作, 不少题目是真的能够靠这个救命的;
Assuming after traversing the 1st level, nodes in queue are {9, 20, 8}, And we are going to traverse 2nd level, which is even line and should print value from right to left [8, 20, 9].
We know there are 3 nodes in current queue, so the vector for this level in final result should be of size 3.
Then, queue [i] -> goes to -> vector[queue.size() - 1 - i]
i.e. the ith node in current queue should be placed in (queue.size() - 1 - i) position in vector for that line.For example, for node(9), it’s index in queue is 0, so its index in vector should be (3-1-0) = 2.
这个想法好像不错, 那是不是意思就是直接可以用array了?
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
if (root == NULL) {
return vector<vector<int> > ();
}
vector<vector<int> > result;
queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
bool leftToRight = true;
while ( !nodesQueue.empty()) {
int size = nodesQueue.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();
// find position to fill node's value
int index = (leftToRight) ? i : (size - 1 - i);
row[index] = node->val;
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}
// after this level
leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}
大概看了一下, 好像真的就是用一个类似array的东西实现的, 可能c++里面的vector就是这么好用? 如果是我可能就直接用array; 反正这个想法还是挺好的;
这个做法最后速度应该是完全不输给Deque的;
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean order = true;
int size = 1;
while(!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {
tmp.add(n.val);
} else {
tmp.add(0, n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
res.add(tmp);
size = q.size();
order = order ? false : true;
}
return res;
}
}
a few minor nitpicks:
- you can initialize variable size inside the while loop : int size = q.size(); and remove one line at the end of while loop. Since int is immutable it won’t affect the performance at all, since Java has to allocate 32 bits of memory every loop cycle anyway.
- you can replace last line of the while loop with order = !order;
Now the actual reason I am leaving this comment is that I am surprised that this algorithm performs as well and sometimes even faster than my Deque algo. tmp(0, n.val) should be terribly inefficient, since it copies over the entire arraylist every time a new element is inserted. But this approach still shows the same performance as Deque… it’s a mystery to me.arraylist tmp(0, n.val) should be O(n), but it runs faster than using linkedlist tmp(0, n.val), which should be constant time. strange.
use arraylist tmp(0, n.val) : 2ms
use linkedlist tmp(0, n.val): 3ms
for zig, pop_back, push_front, left then right,
for zag, pop_front, push_back, right then left
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
std::deque<TreeNode*> deq;
deq.push_back(root);
int iszig=1;
while(!deq.empty()) {
int sz=deq.size();
iszig=iszig^1;
vector<int> row;
while(sz--) {
if(iszig) { // pop_front, push_back, right then left
root=deq.front();deq.pop_front();
row.push_back(root->val);
if(root->right) deq.push_back(root->right);
if(root->left) deq.push_back(root->left);
}
else { // pop_back, push_front, left then right
root=deq.back();deq.pop_back();
row.push_back(root->val);
if(root->left) deq.push_front(root->left);
if(root->right) deq.push_front(root->right);
}
}
res.push_back(row);
}
return res;
}
没仔细看了, 反正这个题目就是绕点脑子, 本身并不难;
submission基本波动;
Problem Description
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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Difficulty:Medium
Total Accepted:128.1K
Total Submissions:352.3K
Contributor:LeetCode
Companies
microsoftbloomberglinkedin
Related Topics
stacktreebreadth-first search
Similar Questions
Binary Tree Level Order Traversal