LeetCode | Binary Tree Level Order Traversal

题目

Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   /   9  20
    /     15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

有正统的基于广度优先的层次遍历（解法1），也有递归的基于深度优先的结果构造方法（解法2）。

解法1

import java.util.ArrayList;

public class BinaryTreeLevelOrderTraversal {
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
		ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
		solve(root, 0, results);
		return results;
	}

	private void solve(TreeNode root, int level,
			ArrayList<ArrayList<Integer>> results) {
		if (root == null) {
			return;
		}
		if (results.size() < level + 1) {
			results.add(new ArrayList<Integer>());
		}
		results.get(level).add(root.val);
		solve(root.left, level + 1, results);
		solve(root.right, level + 1, results);
	}
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversal {
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
		ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
		Queue<TreeNode> curLevel = new LinkedList<TreeNode>();
		Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();
		if (root == null) {
			return results;
		}
		curLevel.add(root);
		ArrayList<Integer> list = new ArrayList<Integer>();
		while (!curLevel.isEmpty()) {
			TreeNode node = curLevel.poll();
			list.add(node.val);
			if (node.left != null) {
				nextLevel.add(node.left);
			}
			if (node.right != null) {
				nextLevel.add(node.right);
			}
			if (curLevel.isEmpty()) {
				Queue<TreeNode> temp = curLevel;
				curLevel = nextLevel;
				nextLevel = temp;
				results.add(list);
				list = new ArrayList<Integer>();
			}
		}

		return results;
	}
}

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

LeetCode | Binary Tree Level Order Traversal

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