Tuesday, September 24, 2013

Binary Tree Level Order Traversal

Q:
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]
]
A:
 ---------------简单的dfs, 每当看见一个节点,就加到结果上-----------------
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        int height = getHeight(root);
        for(int i =0;i<height;i++){
            all.add(new ArrayList<Integer>());
        }
        dfs(all,root,0);
        return all;
    }
    private void dfs(List<List<Integer>> all, TreeNode root, int level){
        if(root == null)
            return;
        all.get(level).add(root.val);
        dfs(all,root.left,level+1);
        dfs(all,root.right,level+1);
    }
    private int getHeight(TreeNode root){
        if(root == null)
            return 0;
        else
            return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }
}



----------------------------第二遍,-------每次取下来一层,   放到一个Node 的list里,  同时保留Integer的一层---------------------

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> all = new LinkedList();
        if(root == null)
            return all;
        List<TreeNode> lastLevel = new LinkedList();
        List<Integer> l = new LinkedList();
        lastLevel.add(root);
        l.add(root.val);
        all.add(l);
        while(lastLevel.isEmpty() ==false){
            l = new LinkedList();
            List<TreeNode> newLevel = new LinkedList();
            for(TreeNode node:lastLevel){
                if( node.left !=null ){
                    newLevel.add(node.left);
                    l.add(node.left.val);
                }
                if( node.right !=null){
                    newLevel.add(node.right);
                    l.add(node.right.val);
                }
            }
            lastLevel = newLevel;
            if(l.isEmpty()==false)
                all.add(l);
        }
        return all;
    }
}




Mistakes:
 1: 考虑到 stack的特性, 我们在加入的时候,要先push right child ,then left
 2  艹~~~~~~~~~  BFS 是用Queue, 而不是stack, TNND
 3:  每次要在while里重新new一个List, 单纯的clear()的话, ----由于其指针特性,会把all里的结果都clear掉
Learned:
1:   经常出现错误说“cannot create a generic array of .......”

Because of how generics in Java work, you cannot directly create an array of a generic type (such as Map<String, Object>[]). Instead, you create an array of the raw type (Map[]) and cast it to Map<String, Object>[]. This will cause an unavoidable (but suppressible) compiler warning.
This should work for what you need:
Map<String, Object>[] myArray = (Map<String, Object>[]) new Map[10];
You may want to annotate the method this occurs in with @SupressWarnings("unchecked"), to prevent the warning from being shown.

还有一个办法,就是  在new 的时候,不加generic type, 例如: 直接也不进行上面的cast
        Stack<TreeNode>[] twoStack = new Stack[2];

3: Queue is an Interface not a class. ,  so,we cannot use them as class.
Instead, we need use LinkedList or PriorityQueue and etc to simulate it.

No comments:

Post a Comment