package leetcode.easy;

/**

 * Definition for a binary tree node. public class TreeNode { int val; TreeNode

 * left; TreeNode right; TreeNode(int x) { val = x; } }

 */

public class BinaryTreeLevelOrderTraversalII {

	// DFS solution:

	public java.util.List<java.util.List<Integer>> levelOrderBottom1(TreeNode root) {

		java.util.List<java.util.List<Integer>> wrapList = new java.util.LinkedList<java.util.List<Integer>>();

		levelMaker(wrapList, root, 0);

		return wrapList;

	}

	private static void levelMaker(java.util.List<java.util.List<Integer>> list, TreeNode root, int level) {

		if (root == null) {

			return;

		}

		if (level >= list.size()) {

			list.add(0, new java.util.LinkedList<Integer>());

		}

		levelMaker(list, root.left, level + 1);

		levelMaker(list, root.right, level + 1);

		list.get(list.size() - level - 1).add(root.val);

	}

	// BFS solution:

	public java.util.List<java.util.List<Integer>> levelOrderBottom2(TreeNode root) {

		java.util.Queue<TreeNode> queue = new java.util.LinkedList<TreeNode>();

		java.util.List<java.util.List<Integer>> wrapList = new java.util.LinkedList<java.util.List<Integer>>();

		if (root == null) {

			return wrapList;

		}

		queue.offer(root);

		while (!queue.isEmpty()) {

			int levelNum = queue.size();

			java.util.List<Integer> subList = new java.util.LinkedList<Integer>();

			for (int i = 0; i < levelNum; i++) {

				if (queue.peek().left != null) {

					queue.offer(queue.peek().left);

				}

				if (queue.peek().right != null) {

					queue.offer(queue.peek().right);

				}

				subList.add(queue.poll().val);

			}

			wrapList.add(0, subList);

		}

		return wrapList;

	}

	@org.junit.Test

	public void test() {

		TreeNode tn11 = new TreeNode(3);

		TreeNode tn21 = new TreeNode(9);

		TreeNode tn22 = new TreeNode(20);

		TreeNode tn33 = new TreeNode(15);

		TreeNode tn34 = new TreeNode(7);

		tn11.left = tn21;

		tn11.right = tn22;

		tn21.left = null;

		tn21.right = null;

		tn22.left = tn33;

		tn22.right = tn34;

		tn33.left = null;

		tn33.right = null;

		tn34.left = null;

		tn34.right = null;

		System.out.println(levelOrderBottom1(tn11));

		System.out.println(levelOrderBottom2(tn11));

	}

}