Leetcode 102题.Binary Tree Level Order Traversal

dfs和bfs

方法一：递归宽度优先搜索

方法一：递归

每一层从左往右遍历，先遍历左子树再遍历右子树，自顶向下root为第0层，依次增加，每一层作为一个vector< int>类型的容器。代码如下：

class Solution{ public: vector<vector<int>> levelOrder(TreeNode* root){ vector<vector<int>> result; int num = 0; traversal(root, result, num); return result; } void traversal(TreeNode* tree, vector<vector<int>>& res, int level) { if(tree == NULL) return; if (level >= res.size()) res.push_back(vector<int>()); res[level].push_back(tree->val); traversal(tree->left, res, level+1); traversal(tree->right, res, level+1); } };

其中，if语句的添加是为了避免下标访问过界。不添加该语句未实现对res的自动扩容。

if (level >= res.size()) res.push_back(vector<int>());

实现结果：

宽度优先搜索

利用队列先进先出的思想(queue的用法详解)，自顶向下从左往右依次访问添加元素。 代码：

class Solution{ public: vector<vector<int>> levelOrder(TreeNode* root){ vector<vector<int>> result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int num = q.size(); result.push_back(vector<int>());//扩容，使back()进入下一维 for(int i = 0; i < num; i++) { auto tree = q.front(); q.pop(); result.back().push_back(tree->val); if(tree->left) q.push(tree->left); if(tree->right) q.push(tree->right); } } return result; } };