二叉树的层序遍历

发布于 2021-03-11 00:02:12   阅读量 39  点赞 0  

问题介绍

 即获取二叉树每一层的节点。

 如给定二叉树:[3,9,20,null,null,15,7]

 其层序遍历结果为:

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


思路

 使用特殊的广度优先搜索(BFS):

  • 根元素入列

  • 当队列不为空的时候,取出队列中所有 s_i 个元素进行拓展,将子节点添加到队列

  • 不断迭代

 以上算法与普通的广度优先搜索的区别在于,普通广度优先搜索每次只取一个元素拓展,而这里一次取 s_i 个元素,这所有 s_i 个元素就是一层节点的集合。


代码

 只需在每次迭代前记录当前队列的长度,即可模拟迭代过程中取出当前队列所有元素。

vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> result;

    if(!root)
        return result;

    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()){
        vector<int> currentLevel;
        int currentSize = q.size();
        for(int i=0; i<currentSize; i++){
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            if(node->left)
                q.push(node->left);
            if(node->right)
                q.push(node->right);
        }
        result.push_back(currentLevel);
    }

    return result;
}


Last Modified : 2021-03-12 10:59:09