103. Binary Tree Zigzag Level Order Traversal
3050 ワード
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> results = new ArrayList<List<Integer>>();
// add the root element with a delimiter to kick off the BFS loop
LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
node_queue.addLast(root);
node_queue.addLast(null);
LinkedList<Integer> level_list = new LinkedList<Integer>();
boolean is_order_left = true;
while (node_queue.size() > 0) {
TreeNode curr_node = node_queue.pollFirst();
if (curr_node != null) {
if (is_order_left)
level_list.addLast(curr_node.val);
else
level_list.addFirst(curr_node.val);
if (curr_node.left != null)
node_queue.addLast(curr_node.left);
if (curr_node.right != null)
node_queue.addLast(curr_node.right);
} else {
// we finish the scan of one level
results.add(level_list);
level_list = new LinkedList<Integer>();
// prepare for the next level
if (node_queue.size() > 0)
node_queue.addLast(null);
is_order_left = !is_order_left;
}
}
return results;
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Zigzag Level Order Traversal.Memory Usage: 39.8 MB, less than 6.09% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
Reference
この問題について(103. Binary Tree Zigzag Level Order Traversal), 我々は、より多くの情報をここで見つけました https://velog.io/@jwade/103.-Binary-Tree-Zigzag-Level-Order-Traversalテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol