【LeetCode 102】Binary Tree Level Order Traversal (C++)

87 阅读 0 评论 58 点赞

我是靠谱客的博主潇洒康乃馨，这篇文章主要介绍【LeetCode 102】Binary Tree Level Order Traversal (C++)，现在分享给大家，希望可以做个参考。

Problem:

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

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

复制代码

return its level order traversal as:

复制代码

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

Solution:

用一个队列实现，很难用栈实现，因为需要保证同层的有序插入

复制代码

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
/**
* 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>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> q;
if(root==NULL)return result;
q.push(root);
while(!q.empty()){
result.push_back(vector<int>());
int s,deep;
s=q.size();
deep=result.size()-1;
while(s>0){
TreeNode* t=q.front();
q.pop();
result[deep].push_back(t->val);
if(t->left!=NULL)q.push(t->left);
if(t->right!=NULL)q.push(t->right);
s--;
}
}
return result;
}
};