题目

题目思路

一次for循环，将存在queue中的元素全部出完，并存到临时数组队列tep中，
并将下一层的全部节点存入queue 中，这样，每一次queue中都只会存入一层的结点，
并用len=queue.size()来记录queue中结点数，即为一层的结点数，
同时为一次for循环的次数，从而达到出完queue中一层结点，又存入下一层结点的效果。
一次while循环，将存到tep中的一层结点数存入返回结果res中。

小夕有话说：这道题本质是要知道每层的长度，这样达到长度以后即把这层的全部数字产出即可。为了记录下一次的长度，一种思路是用临时变量的存下来的长度是多少，另一种方法是使用队列的长度即可。本文的第一种方式是使用队列长度。

图解思路

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/

屏幕捕获_2020_12_30_23_32_19_724.png

屏幕捕获_2020_12_30_23_32_22_373.png

屏幕捕获_2020_12_30_23_32_24_573.png

屏幕捕获_2020_12_30_23_32_27_170.png

屏幕捕获_2020_12_30_23_32_29_706.png

屏幕捕获_2020_12_30_23_32_32_137.png

屏幕捕获_2020_12_30_23_32_34_71.png

屏幕捕获_2020_12_30_23_32_35_987.png

屏幕捕获_2020_12_30_23_32_38_53.png

屏幕捕获_2020_12_30_23_32_40_486.png

动画

录制_2020_12_30_23_32_49_480.gif

代码

Java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

C++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> res;
        while(q.size())
        {
            int size=q.size();
            vector<int> level;
            for(int i=0;i<size;i++)
            {
                TreeNode* rt=q.front();q.pop();
                if(!rt) continue;
                level.push_back(rt->val);
                if(rt->left) q.push(rt->left);
                if(rt->right) q.push(rt->right);
            }
            if(level.size()!=NULL) res.push_back(level);
        }
        return res;
    }
};

Python

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res

JS

// ac地址：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
// 原文地址：https://xxoo521.com/2020-02-20-level-travel/

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const queue = [root];
    const res = []; // 存放遍历结果
    let level = 0; // 代表当前层数
    while (queue.length) {
        res[level] = []; // 第level层的遍历结果

        let levelNum = queue.length; // 第level层的节点数量
        while (levelNum--) {
            const front = queue.shift();
            res[level].push(front.val);
            if (front.left) queue.push(front.left);
            if (front.right) queue.push(front.right);
        }

        level++;
    }
    return res;
};