[LeetCode]Binary Tree Level Order Traversal II

迭代的版本可以在level order i的基础上最后用stack倒一下就行。不过我们选择用LinkedList的话，直接在头加就可以了，O(1)时间。
递归的版本只要注意是向哪个list里插，其他和I是一样的。从root到node的深度差是不会变得，所以该插入的list到结果集最后的list的距离也是不变的。

代码如下：

iterative

	/**
	* 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>> levelOrderBottom(TreeNode root) {
	List<List<Integer>> res = new LinkedList<List<Integer>>();
	if (root == null)
	return res;
	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	queue.add(root);
	while (true) {
	res.add(0, new LinkedList<Integer>());
	int size = queue.size();
	for (int i = 0; i < size; i++) {
	TreeNode temp = queue.removeFirst();
	res.get(0).add(temp.val);
	if (temp.left != null)
	queue.add(temp.left);
	if (temp.right != null)
	queue.add(temp.right);
	}
	if (queue.isEmpty())
	break;
	}
	return res;
	}
	}

view raw bst level order traversal ii iterative.java hosted with ❤ by GitHub

recursive

	public class Solution {
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
	List<List<Integer>> res = new LinkedList<List<Integer>>();
	dfs(res, root, 1);
	return res;
	}
	private void dfs(List<List<Integer>> res, TreeNode node, int level) {
	if (node == null)
	return;
	if (level > res.size())
	res.add(0, new LinkedList<Integer>());
	res.get(res.size() - level).add(node.val);
	dfs(res, node.left, level + 1);
	dfs(res, node.right, level + 1);
	return;
	}
	}

view raw bst level order traversal ii recursive.java hosted with ❤ by GitHub