题目描述

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

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

解法

题目要求按层遍历，传统的DFS也可以解，但是没有那么自然。我们用一个deque（可以先进先出）, 按顺序压入节点，设level_count为每层的节点数，vector v为每层的节点值集合，每访问一个节点操作：level_count –；v.push_back(node->val); deque.pop_front();，当level_count == 0时，说明一层已经访问完毕, 操作：result.push_back(v); v.clear(); 更新level_count = 下一层节点数；

代码

void traversalNext(TreeNode* node, deque& node_stack) {
    if (node->left) {
        node_stack.push_back(node->left);
    }
    if (node->right) {
        node_stack.push_back(node->right);
    }
}

vector> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    vector<int> v;
    int level_count = 0;
    if (root == NULL) return result;
    deque<<TreeNode*> node_stack;
    node_stack.push_back(root);
    level_count = node_stack.size();
    while (!node_stack.empty()) {
        TreeNode* node = node_stack.front();
        v.emplace_back(node->val);
        node_stack.pop_front();
        level_count--;
        if (level_count == 0) {
            result.push_back(v);
            v.clear();
            traversalNext(node, node_stack);
            level_count = node_stack.size();
        }
        else {
            traversalNext(node, node_stack);
        }
    }
    return result;
}

扩展

上面说过，这道题也是可以用DFS解的，只是初看不那么自然。分享我的一段面试经历，面试官出了这么一道题，给出一个二叉树的左视图，左视图就是从树的左边往右看，看到的节点。转换一下，就是每层的第一个节点。我当时第一反应就是DFS遍历树，并给出了解法。面试官感觉水平不高，没看太明白（连

vector<vector<int>> result;

这种结构都不是很清楚），让我用循环迭代，我居然也没给出来，真是悔恨…

DFS的解法

依然是vector<vector<int>> result; 存放结果，
int level；当前的层数，
然后前序遍历DFS，对于面试题，我们设i为层，只要依次返回result[i][0]即可。

代码

void traversalDFS(TreeNode* node, int level, vector<vector<int>>& result) {
    if (node == NULL) {
        return;
    }
    if (level > result.size())
        result.push_back(vector());
    result[level-1].push_back(node->val);
    traversalDFS(node->left, level + 1, result);
    traversalDFS(node->right, level + 1, result);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    traversalDFS(root, 1, result);
    return result;
}

效率：实际上这个解法的效率比一开始给出的伪迭代解法效率要高，也是出乎我的意料，分析一下，应该是伪迭代用了deque来模拟栈，还不如正统的栈来得快。附上leetcode提交结果：
执行用时 : 4 ms, 在所有 C++ 提交中击败了 92.97%的用户
内存消耗 : 14.9 MB, 在所有 C++ 提交中击败了11.32%的用户
伪迭代只有60%, 但是内存消耗要低一些。