层序遍历(广度优先搜索)-102

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

解题思路

这里我们层次遍历我们需要使用到队列这个数据结构，我们依次从根节点开始遍历，我们需要使用一个变量来记录此时我们队列中元素的数量，因为这样我们才知道这一层我们需要从队列中弹出多少个元素，弹出的元素我们加入到集合中，然后再把弹出元素的左右孩子节点依次添加到我们的队列中，当然这里我们还要判断遍历结束的条件–就是当我们这一层的所有元素都没有左右孩子节点就结束我们的遍历了

代码实例

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }
        // TreeNode index=root;
        Queue<TreeNode> queue = new LinkedList<>();
        //用来判断遍历终止的条件
        int judge = 1;
        queue.add(root);
        while (judge != 0) {
            int size = queue.size();
            //用来判断遍历终止的条件
            int xiao = 0;
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i <= size; i++) {
                TreeNode temp = queue.poll();
                list.add(temp.val);
                if (temp.left != null) {
                    queue.add(temp.left);
                    xiao = 1;
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                    xiao = 1;
                }

            }
            result.add(list);
            if (xiao == 1) {
                judge = 1;
            } else {
                judge = 0;
            }
        }
        return result;
    }
}