[매일 한 문제] 층층이 훑어보다.

2326 단어 문제를 풀다
앞의 문장에서 나는 두 갈래 나무의 간단한 함수 실현을 실현한 적이 있는데, 여기서 상세하게 소개하지 않겠습니다. 잘 모르는 것은 스탬프를 주십시오https://blog.csdn.net/dove1202ly/article/details/79133089
오늘은 주로 [층층이 두루 훑어보기]---> 면접 상시 시험, 반드시 해야 합니다^_^
[제목] 두 갈래 나무를 정하고 그 노드 값이 밑에서 위로 올라가는 차원으로 되돌아간다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다)
예를 들어 두 갈래 나무를 지정합니다[3,9,20,null,null,15,7] ,
    3
   / \
  9  20
    /  \
   15   7

다음 단계를 반복하여 맨 위에서 아래로 돌아갑니다.
[
  [3]
  [9,20],
  [15,7],
]

아래에서 위로 올라가는 단계를 다음과 같이 되돌려줍니다.
[
  [15,7],
  [9,20],
  [3]
]

【코드 구현】
#include
using namespace std;
#include
#include
#include
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 // 
 //class Solution {
 //public:
	// vector> levelOrder(TreeNode* root) {
	//	 vector> result;// ; ,result 
	//	 if (NULL == root)
	//	 {
	//		 return result;
	//	 }
	//	 // ---》 
	//	 queue qu;
	//	 qu.push(root);// ;
	//	 while (!qu.empty())
	//	 {
	//		 vector tmp;// 
	//		 int sz = qu.size();
	//		 while (sz--)
	//		 {
	//			 // 
	//			 TreeNode* topnode = qu.front();
	//			 qu.pop();
	//			 tmp.push_back(topnode->val);
	//			 if (topnode->left)
	//			 {
	//				 qu.push(topnode->left);
	//			 }
	//			 if (topnode->right)
	//			 {
	//				 qu.push(topnode->right);
	//			 }
	//		 }
	//		 result.push_back(tmp);
	//	 }
	//	 return result;
	// }
 //};
 // 
class Solution {
public:
	vector> levelOrder(TreeNode* root) {
		vector> result;
		if (NULL == root)
		{
			return result;
		}
		queue qu;
		qu.push(root);
		while (!qu.empty())
		{
			vector tmp;
			int sz = qu.size();
			while (sz--)
			{
				// 
				TreeNode* topnode = qu.front();
				qu.pop();
				tmp.push_back(topnode->val);
				if (topnode->left)
				{
					qu.push(topnode->left);
				}
				if (topnode->right)
				{
					qu.push(topnode->right);
				}
			}
			result.push_back(tmp);
		}
		// , 
		reverse(result.begin(), result.end());
		return result;
	}
};

좋은 웹페이지 즐겨찾기