首页 > 代码库 > [LeetCode#103]Binary Tree Zigzag Level Order Traversal
[LeetCode#103]Binary Tree Zigzag Level Order Traversal
The problem:
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]]
Soltuion 1:
public class Solution { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>> (); if (root == null) return ret; TreeNode cur_node; ArrayList<Integer> item = new ArrayList<Integer> (); Queue<TreeNode> queue = new LinkedList<TreeNode> ();//Queue is abstract class! queue.offer(root); int cur_num = 1; int next_num = 0; while (queue.size() > 0) { cur_node = queue.poll(); item.add(cur_node.val); cur_num --; if (cur_node.left != null) { queue.offer(cur_node.left); next_num ++; } if (cur_node.right != null) { queue.offer(cur_node.right); next_num ++; } if (cur_num == 0) { ret.add(item); cur_num = next_num; next_num = 0; item = new ArrayList<Integer> (); } } for (int i = 0; i < ret.size(); i++) { if (i % 2 == 1) Collections.reverse(ret.get(i)); } return ret; }}
My analysis for solution2:
The problem could also use two stacks to solve. The main ideas of using two stacks are following:1. use two stacks, one stack for odd level and one stack for even level. since the odd levels and even levels interleave with each other, we don‘t need two worry one level‘s node would mixed with another level‘s node.Stack<TreeNode> stack1 = new Stack<TreeNode> ();Stack<TreeNode> stack2 = new Stack<TreeNode> ();2. we use a cur_level to indicate which the level we are currently in. int cur_level = 0;we update it when we about to enter the new level.if (cur_num == 0) { ret.add(item); cur_num = next_num; next_num = 0; cur_level ++; item = new ArrayList<Integer> ();}3. to reach the goal of ZigZag traversal, 3.1 when we are in odd level, we add the node‘s child from left to right. (stack would reverse it) 3.2 when we are in even level, we add the node‘s child from right to left. (stack would reverse it)
My solution2:
public class Solution { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>> (); if (root == null) return ret; TreeNode cur_node; ArrayList<Integer> item = new ArrayList<Integer> (); Stack<TreeNode> stack1 = new Stack<TreeNode> (); Stack<TreeNode> stack2 = new Stack<TreeNode> (); int cur_num = 1; int next_num = 0; int cur_level = 0; stack1.push(root); while (stack1.size() != 0 || stack2.size() != 0) { if (cur_level % 2 == 0) { cur_node = stack1.pop(); item.add(cur_node.val); cur_num --; if (cur_node.left != null) { //add the next level‘s node into stack2 (from left to right) stack2.push(cur_node.left); next_num ++; } if (cur_node.right != null) { stack2.push(cur_node.right); next_num ++; } } else { cur_node = stack2.pop(); item.add(cur_node.val); cur_num --; if (cur_node.right != null) {//add the next level‘s node into stack1 (from right to left) stack1.push(cur_node.right); next_num ++; } if (cur_node.left != null) { stack1.push(cur_node.left); next_num ++; } } if (cur_num == 0) { ret.add(item); cur_num = next_num; next_num = 0; cur_level ++; item = new ArrayList<Integer> (); } } return ret; }}
[LeetCode#103]Binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。