[数据结构与算法]二叉树的层序遍历

题目描述

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

示例：
二叉树：[3,9,20,null,null,15,7],

3
 / \
 9  20
/  \
15   7

返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1.创建一个queue队列，把root先放进去。
2.当queue不为空时，进入循环。
用size记录下当前层的元素个数
创建ArrayList（flg），目的是把当前层的元素弹出后放入这里，最后放入ret中。
for循环，条件是i < size。
每次弹出queue的元素放入flg，把他的左右不为空的左右结点放入queue中。
当本层元素都弹出后，把flg放入ret中。

*
外层while控制的是层遍历
内部for控制的是当前层的每个节点，所以我们要用size控制遍历的是当前层，而不是下一层的元素。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        //
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.add(root);
        while(!queue.isEmpty()) {
            //记录队列的元素个数，后面需要把当此的元素都弹出去。
            int size = queue.size();
            //每次弹出的元素放入flg中，当本次结束后放入ret中
            List<Integer> flg = new ArrayList<>();
            for(int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                flg.add(t.val);
                //把当前t的不为空的左右子树加入到队列queue中。
                if(t.left != null) {
                    queue.add(t.left);
                }
                if(t.right != null) {
                    queue.add(t.right);
                }
            }
            //此时当前队列的元素全部弹完，将flg放入到ret中。
            ret.add(flg);
        }
        return ret;
    }
}