LeetCode: Binary Search 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]
]

This is an easy one. Solved it with two solutions

	//iterative solution
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	if(root == null) return res;
	Queue<TreeNode> que = new LinkedList<TreeNode>();
	TreeNode dumbNode = new TreeNode(0);
	ArrayList<Integer> al = new ArrayList<Integer>();
	que.add(root);
	que.add(dumbNode);
	while(!que.isEmpty()){
	TreeNode node = que.remove();
	if(node == dumbNode){//end of a level
	res.add(al);
	if(!que.isEmpty()){
	que.add(dumbNode);
	al = new ArrayList<Integer>();
	}
	}
	else{
	al.add(node.val);
	if(node.left != null){
	que.add(node.left);
	}
	if(node.right != null){
	que.add(node.right);
	}
	}
	}
	return res;
	}
	//recursive solution
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	if(root == null) return res;
	levelOrderRec(res, root, 0);
	return res;
	}
	public void levelOrderRec(ArrayList<ArrayList<Integer>> res, TreeNode root, int levelOrder) {
	if(root == null) return;
	int len = res.size();
	if(levelOrder==len){
	ArrayList<Integer> al= new ArrayList<Integer>();
	al.add(root.val);
	res.add(al);
	}
	else if(levelOrder < len){
	res.get(levelOrder).add(root.val);
	}
	levelOrderRec(res, root.left, levelOrder+1);
	levelOrderRec(res, root.right, levelOrder+1);
	}

view raw gistfile1.java hosted with ❤ by GitHub