두 갈래 트리를 정해서 차원별로 훑어보는 노드 값을 되돌려줍니다.(즉, 왼쪽에서 오른쪽으로 모든 노드에 층층이 접근한다.)
1790 단어 매일 한 문제를 힘껏 풀다.
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],
3/\9 20/\15 7은 다음 단계를 반복합니다.
[ [3], [9,20], [15,7] ]
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
문제 해결 방법:
이 문제는 이전의 층차보다 한 걸음 더 많이 조작되었다. 그것은 바로 출력할 때 층차적으로 출력하는 것이다.우리는 인쇄에 간단하게 숫자에 따라 출력할 수 없다. 예를 들어 1층은 1개, 2층은 2개, 3층은 4개를 출력한다.실제 층마다 원소가 하나씩 있으면 출력해야 한다.
회상층이 두루 돌아다니는 방법은 두결점과 그의 좌우 아이 노드를 모두 대열에 넣은 다음에 두 노드를 인쇄하고 두 노드를 대열로 나가는 것이다. 여기서 우리는 온전한 두 갈래 나무를 하나의 최소 두 갈래 나무로 볼 수 있기 때문에 두 노드는 전체 두 갈래 나무의 두 노드만 가리키는 것이 아니라 모든 최소 두 갈래 나무의 두 노드를 가리킨다.대열의 특징에 따라 먼저 들어가고 먼저 나가면 층차를 잘 완성할 수 있다.
그러나 층차에 따라 출력하는 것은 문제이다. 1층 대기열의 길이는 1이고 1층 대기열이 나간 후에 남은 것은 다음 층의 모든 요소이며 대기열의 길이에 따라 각 줄의 출력 개수를 제어할 수 있다는 것을 알 수 있다.
#include
#include
#include
using namespace std;
class Solution {
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL)
{}
};
public:
vector> levelOrder(TreeNode* root)
{
vector> res;
if (!root)
{
return res;
}
vector vtmp;
/* , */
queue qu;
TreeNode* cur=root;
qu.push(root);
int len = 1;
/* */
while ( !qu.empty())
{
/* vector */
for (int i = 0; i < len; ++i)
{
cur = qu.front();
vtmp.push_back(cur->val);
qu.pop();
if (cur->left)
{
qu.push(cur->left);
}
if (cur->right)
{
qu.push(cur->right);
}
}
res.push_back(vtmp);
vtmp.clear();
len = qu.size();
}
return res;
}
};
int main()
{
system("pause");
return 0;
}