首页 > 其他 > 详细

LeetCode | Binary Tree Zigzag Level Order Traversal

时间:2014-03-03 16:47:44      阅读:426      评论:0      收藏:0      [点我收藏+]

题目

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]
]
分析

从遍历顺序上看,直接想到BFS和栈,实现时遍历顺序还是需要耐心确认的。

代码

import java.util.ArrayList;
import java.util.Stack;

public class BinaryTreeZigzagLevelOrderTraversal {
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
		ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
		if (root == null) {
			return results;
		}
		Stack<TreeNode> currentLevel = new Stack<TreeNode>();
		Stack<TreeNode> nextLevel = new Stack<TreeNode>();
		boolean reverse = false;
		ArrayList<Integer> list = new ArrayList<Integer>();
		currentLevel.push(root);
		while (!currentLevel.isEmpty()) {
			TreeNode node = currentLevel.pop();
			list.add(node.val);
			if (reverse) {
				if (node.right != null) {
					nextLevel.push(node.right);
				}
				if (node.left != null) {
					nextLevel.push(node.left);
				}
			} else {
				if (node.left != null) {
					nextLevel.push(node.left);
				}
				if (node.right != null) {
					nextLevel.push(node.right);
				}
			}

			if (currentLevel.isEmpty()) {
				Stack<TreeNode> temp = currentLevel;
				currentLevel = nextLevel;
				nextLevel = temp;
				results.add(new ArrayList<Integer>(list));
				list.clear();
				reverse = !reverse;
			}
		}
		return results;
	}
}


LeetCode | Binary Tree Zigzag Level Order Traversal,布布扣,bubuko.com

LeetCode | Binary Tree Zigzag Level Order Traversal

原文:http://blog.csdn.net/perfect8886/article/details/20306335

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!