BFS和DFS两种方式实现二叉树的层序遍历

迈不过友情╰ 2022-11-10 10:48 87阅读 0赞

**二叉树文章系列：**

1.  [二叉树的前序遍历][Link 1]
2.  [二叉树的中序遍历][Link 2]
3.  [二叉树的后序遍历][Link 3]
4.  [二叉树的层序遍历][Link 4]
5.  [二叉树的前序、中序、后序、层序遍历【解法完整版】][Link 5]

### 本文目录 ###

*   *  前言
     *  一、题目
     *  二、思路分析
     *   *  解法一：广度优先搜索BFS
         *  解法二：深度优先搜索DFS
     *  三、总结

## 前言 ##

这是\[LeetCode精选Top面试\]系列文章的第1篇/145篇。  
在这个系列中，我们会按照题目类别进行总结。对于每一道题目，会给出一种或多种的算法思路，以及最精炼、最高效的代码。如果代码中涉及到语言上的语法知识，我们也会在知识扩展小节中进行详解。  
在每个系列介绍完成之后，我们会再次回顾总结，提炼出通用解法和代码模板。  
希望各位持续关注本系列，和我们一起前进，DayDayUp~

## 一、题目 ##

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

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

3
     / \
    9  20
       /  \
      15   7

返回其层次遍历结果：

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

## 二、思路分析 ##

### 解法一：广度优先搜索BFS ###

广度优先搜索是从树的根节点开始，**沿着树的宽度**来遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索通常采用**队列**来辅助实现。

在题目中要求按照层序遍历，实现逐层地从左向右访问所有的结点。这正好符合广度优先搜索的策略。

我们可以立即想到普通广度优先搜索的模板：

vector<int> bfs(TreeNode* root) {
            
        std::vector<int> result;
        if(!root){
            return result;
        }   
    
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            result.emplace_back(node->val);
            if(node->left){
                q.push(node->left);
            }            
            if(node->right){
                q.push(node->right);
            }
        }
        return result;
    }

但是，这里返回的是一个一维数组，和题目要求的二维数组不一致。因此，我们需要稍作修改，修改内容如下：

*  在while循环每次遍历时，获取队列的长度N（即队列中的节点个数）
 *  一次性的处理这N个节点，然后再进入下一轮循环。

通过这种修改，确保每次循环时要处理的队列中元素都是本层的元素。

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> tmp;
            // 每次q.size() 获取的都是队列的长度（一个层的节点个数）
            for(int i = q.size(); i > 0 ; i--){
                TreeNode* node = q.front();
                q.pop();
                tmp.emplace_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            result.emplace_back(tmp);
        }
        return result;
    
    }

![e51aa53d657b7a36a064932dcdd79ff1.png][]

**复杂度分析：**

*  时间复杂度：每个节点元素进队和出队操作各一次，时间复杂度为 O ( N ) O(N) O(N)。
 *  空间复杂度：队列最大存储个数小于等于N，空间复杂度为 O ( N ) O(N) O(N)。

### 解法二：深度优先搜索DFS ###

本题也可以使用深度优先搜索来实现。

深度优先搜索是采用栈或者递归来实现。（递归在系统内部也是基于栈来实现）

vector<vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> res;
        if(!root) return res;
        dfs(0, root, res);
        return res;
    }
    
    // index 是节点所在层的层索引
    void dfs(int index, TreeNode* node, std::vector<std::vector<int>>& res){
        // node 应该放到res[index]中, 如果res[index]元素不存在, 需要先创建一个
        if(res.size() < index + 1){
            res.push_back({});
        }
        res[index].emplace_back(node->val);
        if(node->left){
            dfs(index+1, node->left, res);
        }
        if(node->right){
            dfs(index+1, node->right, res);
        }
    }

![cf6068591b32bb0095b42b786e8cbebf.png][]

**复杂度分析：**

*  时间复杂度：在递归过程中每个节点只访问一次，所以时间复杂度为 O ( N ) O(N) O(N)。
 *  空间复杂度：系统栈的最大存储节点数小于等于N, 所以空间复杂度为 O ( N ) O(N) O(N)。

## 三、总结 ##

1.  了解广度优先搜索和深度优先搜索的思想。
2.  了解两种实现的算法模板，广度优先搜索通常使用队列来实现，深度优先搜索通常使用递归实现。
3.  能够根据题干的要求，在模板的基础上灵活调整。

[Link 1]: https://blog.csdn.net/u010414589/article/details/115415226
[Link 2]: https://blog.csdn.net/u010414589/article/details/115415373
[Link 3]: https://blog.csdn.net/u010414589/article/details/115415388
[Link 4]: https://blog.csdn.net/u010414589/article/details/114905914
[Link 5]: https://blog.csdn.net/u010414589/article/details/115415401
[e51aa53d657b7a36a064932dcdd79ff1.png]: /images/20221023/a0b2c77fd49e48d39ad79d2ec6d9b734.png
[cf6068591b32bb0095b42b786e8cbebf.png]: /images/20221023/2fa515895f194154a77619155eda7c0c.png