두 갈래 트리를 정해서 차원별로 훑어보는 노드 값을 되돌려줍니다.(즉, 왼쪽에서 오른쪽으로 모든 노드에 층층이 접근한다.)

두 갈래 트리를 정해서 차원별로 훑어보는 노드 값을 되돌려줍니다.(즉, 왼쪽에서 오른쪽으로 모든 노드에 층층이 접근한다.)
예를 들어 두 갈래 나무를 주면[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;
}

좋은 웹페이지 즐겨찾기