검지 32-1 위에서 아래로 두 갈래 나무 인쇄

5037 단어
위에서 아래로 두 갈래 나무의 각 노드를 인쇄하고, 같은 층의 노드는 왼쪽에서 오른쪽의 순서에 따라 인쇄한다.
 
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],
3/\9 20/\15 7 반환:
[3,9,20,15,7]
 
위에서 아래로 해야 하기 때문에 선진적인 선출을 요구하고, 먼저 눌린 층은 먼저 출력해야 하기 때문에 대열을 채택한다.
첫 번째 층부터 루트 노드의 값을 출력한 다음 왼쪽 트리를 대기열에 눌러 넣습니다 (비워 있지 않은 경우).
그 다음에 층마다 대기열의 길이, 즉 이 층의 노드의 수량을 기록한 다음에 하나씩 튀어나와 이 층의 각 노드에 값을 출력한 다음에 좌우 트리를 눌러 넣는다.이 노드의 수량을 미리 기록했기 때문에 다음 층으로 출력되지 않습니다.
루트 노드가 비어 있는 상황을 주의하십시오.
 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> levelOrder(TreeNode* root) {
13         if(root==nullptr)
14             return {};
15         queue q;
16         vector<int> ret;
17         ret.push_back(root->val);
18         if(root->left!=nullptr)
19             q.push(root->left);
20         if(root->right!=nullptr)
21             q.push(root->right);
22         while(!q.empty()){
23             int cur_size=q.size();
24             while(cur_size!=0){
25                 TreeNode* curptr=q.front();
26                 q.pop();
27                 cur_size--;
28                 ret.push_back(curptr->val);
29                 if(curptr->left!=nullptr)
30                     q.push(curptr->left);
31                 if(curptr->right!=nullptr)
32                     q.push(curptr->right);
33             }
34         }
35         return ret;
36     }
37 };

사고를 통해 각 층의 수량을 기록하는 것은 사실 완전히 헛수고이다. 왜냐하면 본 문제는 층을 나누어 출력하지 않고 다음 층으로 직접 순서를 정하는 것은 전혀 영향을 주지 않기 때문이다.
STL 원자로 작동
AWS의 이벤트 구동 Python

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage