Accepted Java solution. Two stacks instead of recursion.


  • 0
    P

    I use two stacks to avoid recursion. And again the LinkedList is helper make zig-zag order easily.

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    	
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	Stack<TreeNode> nodes = new Stack<TreeNode>();
    	Stack<Integer> levels = new Stack<Integer>();
    	nodes.push(root);
    	levels.push(0);
    	
    	while (!nodes.isEmpty()) {
    		TreeNode node = nodes.pop();
    		int level = levels.pop();
    		if (node == null) continue;
    		
    		if (result.size()-1 < level) result.add(new LinkedList<Integer>());
    		if (level % 2 == 0) {
    			((LinkedList<Integer>) result.get(level)).addLast(node.val);
    		} else {
    			((LinkedList<Integer>) result.get(level)).addFirst(node.val);
    		}
    		
    		nodes.push(node.right);
    		levels.push(level+1);
    		nodes.push(node.left);
    		levels.push(level+1);
    	}
    	
    	return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.