二叉树层级遍历

解题思路

递归写法

1. 遍历时从顶点开始，每层都建立一个新的子数组，用于存放顶点的值
2. 将左二子和右儿子的值加入到数组中
3. 将层级++，递归到子树去执行，同时携带全局数组，逐层给level对应的数组中添加新值

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (root == null) return list;
        addObj(list, 0,root);
        System.out.println(list);
        return list;
    }
    public void addObj(List<List<Integer>> levels,int level,TreeNode node){
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

        List<Integer> temp = levels.get(level);
        int a = node.val;
        temp.add(a);

        if (node.left != null) {
            addObj(levels, level+1, node.left);
        };
        if ( node.right != null) {
            addObj(levels, level+1, node.right);
        }
    }
}

队列写法

1. 建立先进先出队列，将首节点放入（此时队列内只有一个节点）
2. 依次移除队列中所有元素，并新建数组储存移出节点的值，同时将子节点继续拼入到队列中（此时队列有两个节点）
3. 将数组储存到全局数组中。
4. 如果队列不为空，那么重复执行2，3步骤
5. 队列为空了说明所有节点都已经遍历完毕。

代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List list = new ArrayList<>();
        if (root == null) return list;
        LinkedList<TreeNode> deque = new LinkedList<TreeNode>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            for(int i=0;i<size;++i) {
                TreeNode t = deque.remove();
                tmp.add(t.val);
                if(t.left!=null) {
                    deque.add(t.left);
                }
                if(t.right!=null) {
                    deque.add(t.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}