树相关面试题

1.层次遍历二叉树
就是用队列嘛，唯一可能有点问题的就是怎么一层一个数组；每次bfs时，记录一下队列中的元素个数，就表示了这一层有几个结点，然后遍历下一层时指定遍历次数达到本层的结点数目即可，如此反复。

ArrayList> res = new ArrayList<>();
        Deque q = new linkedList<>();
        if(root == null) return res;
        
        q.offerLast(root);
        while(!q.isEmpty()) {
            int size = q.size();
            ArrayList list = new ArrayList<>();
            for (int i = 0; i < size; i ++) {
                TreeNode curr = q.poll();
                if(curr == null) return res;
                list.add(curr.val);
                if(curr.left != null) q.offerLast(curr.left);
                if(curr.right != null) q.offerLast(curr.right);
            }
            res.add(list);
        }
        return res;