Обход бинарного дерева по уровням

Задача:

Дано: бинарное дерево. Вывод: вывести значения узлов в порядке обхода бинарного дерева по уровням.

К примеру, пусть дано следующее бинарное дерево:

    3
   / \
  9  20
    /  \
   15   7

Результат:

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

Решение:

  1. Посетить корень.
  2. Пока мы проходим уровень L, сохраняем уровень L+1 в стек.
  3. Идем на следующий уровень и проходим все ноды на этом уровне.
  4. Повторяем до тех пор пока не будут пройдены все уровни.

Пример на Java:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>(); 
    	if (root == null) {
    		return result;
    	}
        Queue<TreeNode> tmpQueue = new LinkedList<TreeNode>();
	Stack<Queue<TreeNode>> stack = new Stack<Queue<TreeNode>>();
	TreeNode tmp = root;
	tmpQueue.add(tmp);
	stack.push(tmpQueue);
	while (!stack.isEmpty()) {
		tmpQueue = stack.pop();
	        Queue<TreeNode> newQueue = new LinkedList<TreeNode>();
	    	List<Integer> list = new ArrayList<Integer>();
		while (!tmpQueue.isEmpty()) {
			tmp = tmpQueue.poll();
			list.add(tmp.val);
			if (tmp.left != null) {
				newQueue.add(tmp.left);
			}
			if (tmp.right != null) {
				newQueue.add(tmp.right);
			}
		}
		if (!newQueue.isEmpty()) {
			stack.push(newQueue);
		}
		result.add(list);
	}
	tmp = null;
	tmpQueue = null;
        return result;
}
}
LikeMe: