Task

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

Example

For example: Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

1
2
3
4
5

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

Solution

  • 例子如下图： leetcode102

BFS

  • 维护3个vector：
    • curr存储当前层的节点
    • next存储下一层的节点
    • ans存储最终层次遍历的结果
  • 从根节点开始填充curr，同时向ans和next中填充元素，遍历完curr后next是下一层的节点列表，此时交换curr和next的内容，再遍历curr即是遍历下一层
  • 时间复杂度：遍历的是所有节点，O(n)
  • 空间复杂度：curr和next的大小取决于每一层的节点数量，最多为满二叉树的叶子节点数量O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// Runtime: 12 ms, faster than 19.37% of C++ online submissions for Binary Tree Level Order Traversal.
// Memory Usage: 12.6 MB, less than 80.30% of C++ online submissions for Binary Tree Level Order Traversal.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        //声明用到的3个vector
        vector<vector<int>> ans;
        vector<TreeNode *> curr,next;
        //用根节点初始化
        curr.push_back(root);
        //遍历每一层
        while(!curr.empty()){
            //增加一层就向ans中增加一个vector
            ans.push_back({});
            //遍历当前层
            for(TreeNode *node:curr){
                //填充结果数组
                ans.back().push_back(node->val);
                //填充下一层节点的数组
                if(node->left) next.push_back(node->left);
                if(node->right) next.push_back(node->right);
            }
            //将下一层指定为当前层，准备下一次循环
            std::swap(curr,next);
            next.clear();
        }
        return ans;
    }
};

DFS

  • 使用前序/中序/后序遍历二叉树，遍历每个节点时记录它所在的层数。节点在第几层，就是向ans中的第几个vector中添加节点的数值
  • 若ans中vector的数量不够，即小于depth，就向ans中添加空vector
  • 时间复杂度：遍历的是所有节点，O(n)
  • 空间复杂度：递归实现DFS，递归深度取决于树的高度O(h)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Runtime: 8 ms, faster than 55.58% of C++ online submissions for Binary Tree Level Order Traversal.
// Memory Usage: 13.7 MB, less than 8.02% of C++ online submissions for Binary Tree Level Order Traversal.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector<vector<int>> ans;
        DFS(root,0,ans);
        return ans;
    }
private:
    void DFS(TreeNode *root,int depth,vector<vector<int>> &ans){
        //递归终止条件
        if(!root) return;
        //当ans中的数组数少于当前深度时，向其中添加空数组
        while(ans.size()<=depth)
            ans.push_back({});
        //节点在第几层，就向ans的第几个数组中添加节点的值
        ans[depth].push_back(root->val);
        //遍历
        DFS(root->left,depth+1,ans);
        DFS(root->right,depth+1,ans);
    }
};