〇、序

二叉树的层序遍历可借助一个队列，每出队一个结点则将该结点左右子树加入队列。

LeetCode 102.二叉树的层序遍历

一、BFS，借助队列迭代遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> item = new ArrayList<Integer>();
            int len = queue.size();
            while (len > 0) {
                TreeNode temp = queue.poll();
                item.add(temp.val);
                if (temp.left != null) queue.offer(temp.left);
                if (temp.right != null) queue.offer(temp.right);
                --len;
            }
            result.add(item);
        }
        return result;
    }
}

二、DFS，借助栈递归遍历

public List<List<Integer>> result = new ArrayList<List<Integer>>();
public void level(TreeNode node, Integer deep) {  //deep = 0 开始
       if (node == null) return;
       deep++;
       if (result.size() < deep) {
           List<Integer> item = new ArrayList<Integer>();
           result.add(item);
       }
       result.get(deep - 1).add(node.val);
       level(node.left, deep);
       level(node.right, deep);
   }

三、练练手吧！

LeetCode 107.二叉树的层序遍历Ⅱ：与上题相类似，但是需要改变左右结点进队顺序并从List前端插入。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        Deque<TreeNode> que = new ArrayDeque<TreeNode>();
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            List<Integer> itemList = new ArrayList<Integer>();
            while (len > 0) { 
                TreeNode tempNode = que.pop();
                itemList.add(0, tempNode.val);
                if(tempNode.right != null) que.offer(tempNode.right);
                if(tempNode.left != null) que.offer(tempNode.left);
                --len;
            }
            result.add(0, itemList);
        }
        return result;
    }
}

LeetCode 199.二叉树的右视图：同样的方法，当len==1时，可以保证为本层最后一个元素也就是从右边看到的最后一个元素，输出即可。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        Deque<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            while (len > 0) {
                TreeNode tempNode = que.poll();
                if (len == 1) result.add(tempNode.val);
                if (tempNode.left != null) que.offer(tempNode.left);
                if (tempNode.right != null) que.offer(tempNode.right);
                --len;
            }
        }
        return result;
    }
}

LeetCode 637.二叉树的层平均值：每次循环增加一个sum存储该层结点数据和即可。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();
        double sum;
        que.offer(root);
        while(!que.isEmpty()) {
            sum = 0.0;
            int len = que.size();
            for(int i = 0; i < len; i++) {
                TreeNode tempNode = que.poll();
                if(tempNode != null) sum += tempNode.val;
                if(tempNode.left != null) que.offer(tempNode.left);
                if(tempNode.right != null) que.offer(tempNode.right);
            }
            result.add(sum / len);
        }
        return result;
    }
}

LeetCode 429.N叉树的层序遍历：增加对孩子结点的处理。

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            List<Integer> itemList = new ArrayList<>();
            while (len > 0) {
                Node tempNode = que.poll();                
                itemList.add(tempNode.val);
                List<Node> child = tempNode.children;
                if (child == null || child.size() == 0) {
                    len--;
                    continue;
                }
                for (Node c : child) {
                    if (c != null) {
                        que.offer(c);
                    }
                }
                len--;
            }
            result.add(itemList);
        }
        return result;
    }
}