Binary Tree Level Order Traversal II,Leetcode 解题笔记

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

跟第一个版本一样,只不过每次的solution反着插入result就行了。

public class LevelOrderBottom {
	public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
		if (root == null) {
			return result;
		}
 
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
 
		while (!queue.isEmpty()) {
			ArrayList<Integer> level = new ArrayList<Integer>();
			int queueSize = queue.size();
 
			for (int i = 0; i < queueSize; i++) {
				TreeNode node = queue.poll();
				level.add(node.val);
 
				if (node.left != null) {
					queue.offer(node.left);
				}
 
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
 
			result.add(0, level);
		}
 
		return result;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s