欢迎访问LeetCode题解合集
题目描述
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
题解:
这题的关键是怎么判断 第几层 。
有两种解法:深搜 或者 广搜。
法一:
因为 深搜 自带层级之间的关系,搜索树中下层的高度是上层的高度加一,可以利用这个性质来实现。
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> ret;
void dfs( TreeNode* root, int dep ) {
if ( !root ) return;
if ( ret.size() < dep )
ret.emplace_back( vector<int>{} );
ret[dep - 1].emplace_back( root->val );
dfs( root->left, dep + 1 );
dfs( root->right, dep + 1 );
}
vector<vector<int>> levelOrder(TreeNode* root) {
dfs( root, 1 );
return ret;
}
};
/*
时间:4ms,击败:85.22%
内存:12.3MB,击败:9.82%
*/
法二:
层级遍历一般是使用 广搜 ,但是普通的广搜没法区分开上下层,这里就需要做点手脚了。
普通广搜一次只取一个节点扩展,而我们可以考虑一次把一层的节点全部取完。
写法一:
层级之间添加一个标志,比如 NULL
,遇到这个标志就知道一层结束了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push( root );
q.push( NULL );
while ( q.front() ) {
root = q.front(); q.pop();
ret.emplace_back( vector<int>{} );
while ( root ) {
ret.back().emplace_back( root->val );
if ( root->left ) q.push( root->left );
if ( root->right ) q.push( root->right );
root = q.front(); q.pop();
}
q.push( NULL );
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:11.1MB,击败:94.94%
*/
写法二:
记录队列中的元素个数,假设为 size
个,那么将前 size
个元素出队,就是将一层的元素出队,新入队的元素是下一层节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> levelOrder(TreeNode* root) {
if ( !root ) return ret;
queue<TreeNode*> q;
int size;
q.push( root );
while ( q.size() ) {
size = q.size();
ret.emplace_back( vector<int>{} );
for ( int i = 0; i < size; ++i ) {
root = q.front(); q.pop();
ret.back().emplace_back( root->val );
if ( root->left ) q.push( root->left );
if ( root->right ) q.push( root->right );
}
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:11.3MB,击败:78.40%
*/