《剑指offer》-逐层打印二叉树

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

乍一看就是一个BFS，但是因为太久没刷题都忘记了要使用queue来作为空间存储容器了。

先参考milolip的代码，写出这样的solution：



class Solution {

public:

	vector<vector<int> > Print(TreeNode* pRoot) {

		vector<vector<int> > res;

        if(pRoot==NULL){

            return res;

        }

		queue<TreeNode*> Q;

		Q.push(pRoot);

		Q.push(NULL);

		vector<int> v;

		v.push_back(pRoot->val);

		res.push_back(v);

		v.clear();

		while (!Q.empty()){

			TreeNode* node = Q.front();

			Q.pop();

			if (node != NULL){

				//v.push_back(node->val);

				//cout << node->val << ends;

				if (node->left){

					Q.push(node->left);

					v.push_back(node->left->val);

				}

				if (node->right){

					Q.push(node->right);

					v.push_back(node->right->val);

				}

			}

			else if (!Q.empty()){

				//cout << "test " << endl;

				Q.push(NULL);

				res.push_back(v);

				v.clear();

				//cout << endl;

			}

		}

		return res;

	}

};

上面的代码并不太简洁的样子。

另一种写法是从评论区copy来的，又简洁，又非常直观清晰。两层while的嵌套，正好对应到数的层次遍历以及层内逐点遍历。而这种双层嵌套的循环其实并没有增加复杂度，和原来的复杂度是一样的。

class Solution_11 {

public:

	vector<vector<int> > Print(TreeNode* pRoot) {

		vector<vector<int> > res;

		if (pRoot == NULL){

			return res;

		}

		queue<TreeNode*> q;

		q.push(pRoot);

		while (!q.empty()){

			int lo = 0, hi = q.size();

			vector<int> v;

			while (lo++ < hi){

				TreeNode *t = q.front();

				q.pop();

				v.push_back(t->val);

				if (t->left){

					q.push(t->left);

				}

				if (t->right){

					q.push(t->right);

				}

			}

			res.push_back(v);

		}

		return res;

	}

};

测试代码；

void main_solution_11(){

	Solution_11 s = Solution_11();

	TreeNode* a = new TreeNode(8);

	TreeNode* b1 = new TreeNode(6);

	TreeNode* b2 = new TreeNode(10);

	TreeNode* c1 = new TreeNode(5);

	TreeNode* c2 = new TreeNode(7);

	TreeNode* c3 = new TreeNode(9);

	TreeNode* c4 = new TreeNode(1);

	a->left = b1;

	a->right = b2;

	b1->left = c1;

	b1->right = c2;

	b2->left = c3;

	b2->right = c4;

	vector<vector<int> > q = s.Print(a);

	for (int i = 0; i < q.size(); i++){

		for (int j = 0; j < q[i].size(); j++){

			if (j > 0){

				cout << " ";

			}

			cout << q[i][j];

		}

		cout << endl;

	}

}

int main(){

	main_solution_11();

	return 0;

}

巴特西

《剑指offer》-逐层打印二叉树

最新文章

热门文章