剑指Offer JZ60 把二叉树打印成多行 C++实现

题目描述

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

解题思路

方法一：层次遍历

1、思路：用队列层次遍历二叉树。

2、代码：

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:vector<vector<int> > Print(TreeNode* pRoot) {vector<vector<int> > result;if (!pRoot) return result;queue<TreeNode*> que;que.push(pRoot);vector<int> layer;TreeNode *cur = nullptr;while (!que.empty()) {int n = que.size();while (n > 0) {cur = que.front();que.pop();layer.push_back(cur->val);if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);n--;}result.push_back(layer);layer.clear();}return result;}
};

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(n)。