61 lines
1.6 KiB
Java
61 lines
1.6 KiB
Java
/*
|
|
* @lc app=leetcode id=103 lang=java
|
|
*
|
|
* [103] Binary Tree Zigzag Level Order Traversal
|
|
*/
|
|
|
|
// @lc code=start
|
|
/**
|
|
* Definition for a binary tree node.
|
|
* public class TreeNode {
|
|
* int val;
|
|
* TreeNode left;
|
|
* TreeNode right;
|
|
* TreeNode() {}
|
|
* TreeNode(int val) { this.val = val; }
|
|
* TreeNode(int val, TreeNode left, TreeNode right) {
|
|
* this.val = val;
|
|
* this.left = left;
|
|
* this.right = right;
|
|
* }
|
|
* }
|
|
*/
|
|
class Solution {
|
|
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
|
|
if(root == null) {
|
|
return new ArrayList<>();
|
|
}
|
|
boolean reverse = false;
|
|
List<List<Integer>> ret = new ArrayList<>();
|
|
LinkedList<TreeNode> queue = new LinkedList<>();
|
|
queue.add(root);
|
|
TreeNode layerEndNode = null, curNode = null;
|
|
List<Integer> cache = new ArrayList<>();
|
|
while(!queue.isEmpty()) {
|
|
TreeNode tmp = queue.pollFirst();
|
|
cache.addLast(tmp.val);
|
|
if(tmp.left != null) {
|
|
queue.addLast(tmp.left);
|
|
curNode = tmp.left;
|
|
}
|
|
if(tmp.right != null) {
|
|
queue.addLast(tmp.right);
|
|
curNode = tmp.right;
|
|
}
|
|
if(layerEndNode == null || layerEndNode == tmp) {
|
|
layerEndNode = curNode;
|
|
if(reverse) {
|
|
ret.add(cache.reversed());
|
|
} else {
|
|
ret.add(cache);
|
|
}
|
|
cache = new ArrayList<>();
|
|
reverse = !reverse;
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
}
|
|
// @lc code=end
|
|
|