把二叉树打印成多行
把二叉树打印成多行
http://www.nowcoder.com/questionTerminal/445c44d982d04483b04a54f298796288
题目主要信息：
将一棵n个节点的二叉树按照从上到下按层的方式打印，每层按照从左到右的顺序输出。
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：非递归层次遍历（推荐使用）
知识点：队列
队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
思路：
题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue），事实上，队列中的值大有玄机，让我们一起来看看：
- 当根节点进入队列时，队列长度为1，第一层节点数也为1
- 若是根节点有两个子节点，push进队列后，队列长度为2，第二层节点数也为2；若是根节点一个子节点，push进队列后，队列长度为为1，第二层节点数也为1.
- 由此，我们可知，每层的节点数等于进入该层时队列长度，因为刚进入该层时，这一层每个节点都会push进队列，而上一层的节点都出去了。
综上，反过来，每次只要在队列长度内循环，必定是一层，一层访问完毕再更新队列长度即可。
//遍历一层
int n = temp.size();
for(int i = 0; i < n; i++){
p = temp.poll();
row.add(p.val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(p.left != null)
temp.offer(p.left);
if(p.right != null)
temp.offer(p.right);
}
具体做法：
- step 1：如果树为空，则返回空数组，没有任何打印结果。
- step 2：使用队列辅助层次遍历，优先加入二叉树的根节点。
- step 3：从根节点开始，每次进入一层的时候，记录队列的长度即本层的节点数，然后访问相应节点数全在同一个数组中，子节点加入队列中继续排队。
- step 4：每次访问完一层将数组加入二维数组中再进入下一层。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//层次遍历
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
TreeNode head = pRoot;
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
if(head == null)
//如果是空，则直接返回空数组
return res;
//队列存储，进行层次遍历
Queue<TreeNode> temp = new LinkedList<TreeNode>();
temp.offer(head);
TreeNode p;
while(!temp.isEmpty()){
//记录二叉树的某一行
ArrayList<Integer> row = new ArrayList<Integer>();
int n = temp.size();
//因先进入的是根节点，故每层节点多少，队列大小就是多少
for(int i = 0; i < n; i++){
p = temp.poll();
row.add(p.val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(p.left != null)
temp.offer(p.left);
if(p.right != null)
temp.offer(p.right);
}
res.add(row);
}
return res;
}
}
C++实现代码：
class Solution {
public:
//层次遍历
vector<vector<int> > Print(TreeNode* pRoot) {
TreeNode* head = pRoot;
vector<vector<int> > res;
if(head == NULL)
//如果是空，则直接返回空数组
return res;
//队列存储，进行层次遍历
queue<TreeNode*> temp;
temp.push(head);
TreeNode* p;
while(!temp.empty()){
//记录二叉树的某一行
vector<int> row;
int n = temp.size();
//因先进入的是根节点，故每层节点多少，队列大小就是多少
for(int i = 0; i < n; i++){
p = temp.front();
temp.pop();
row.push_back(p->val);
//若是左右孩子存在，则存入左右孩子作为下一个层次
if(p->left)
temp.push(p->left);
if(p->right)
temp.push(p->right);
}
res.push_back(row);
}
return res;
}
};
Python实现代码
class Solution:
def Print(self , pRoot: TreeNode) -> List[List[int]]:
res = []
if pRoot is None:
#如果是空，则直接返回空数组
return res
#队列存储，进行层次遍历
q = [pRoot]
while q:
#记录二叉树的某一行
row = []
n = len(q)
#因先进入的是根节点，故每层节点多少，队列大小就是多少
for i in range(n):
#取出队首
node = q.pop(0)
row.append(node.val)
#若是左右孩子存在，则存入左右孩子作为下一个层次
if node.left:
#加入队尾
q.append(node.left)
if node.right:
q.append(node.right)
res.append(row)
return res
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，每个节点访问一次
- 空间复杂度：，辅助队列的空间最大情况为
方法二：递归层次遍历
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
除了用队列非递归可以实现二叉树的层次遍历，我们也可以使用递归。但是递归前序遍历访问二叉树不是按照层次的顺序，但是因为“根左右”的次序，我们能保证每一层一定左边的元素先访问，后面再访问到同一层右边的元素。
要找到这个节点是第几层的，只是需要在函数中加入记录深度的变量，每往下一层深度加1，同时保存结果的数组正好对应每层一个数组，因此数字的大小正好是遍历的深度，由此可以实现递归。
//递归左右时节点深度记得加1
traverse(root.left, res, depth + 1);
traverse(root.right, res, depth + 1);
具体做法：
- step 1：记录输出的二维数组初始化为空，每到一层里面填出一个一维数组。
- step 2：从根节点开始，深度为1开始进行递归，当前节点有值递归内容才继续进行，否则返回。
- step 3：如果记录输出的二维数组长度小于当前层数，说明要新到了一层，我们新开辟一个一维数组加到最后。
- step 4：因为“根左右”的顺序，同一层左边必定先访问，只需要根据层数在二维数组中找到相应的行号，添加在该行末尾就一定是层次遍历的次序。
Java实现代码：
import java.util.*;
public class Solution {
private void traverse(TreeNode root, ArrayList<ArrayList<Integer> > res, int depth) {
if(root != null){
//数组长度小于当前层数，新开一层
if(res.size() < depth)
res.add(new ArrayList<Integer>());
//数组从0开始计数因此减1，在节点当前层的数组中插入节点
res.get(depth - 1).add(root.val);
//递归左右时节点深度记得加1
traverse(root.left, res, depth + 1);
traverse(root.right, res, depth + 1);
}
}
//层次遍历
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
//树的层级从1开始递归计数
traverse(pRoot, res, 1);
return res;
}
}
C++实现代码：
class Solution {
public:
void traverse(TreeNode* root, vector<vector<int>>& res, int depth) {
if(root){
//数组长度小于当前层数，新开一层
if(res.size() < depth)
res.push_back(vector<int>{});
//数组从0开始计数因此减1，在节点当前层的数组中插入节点
res[depth - 1].push_back(root->val);
//递归左右时节点深度记得加1
traverse(root->left, res, depth + 1);
traverse(root->right, res, depth + 1);
}
}
//层次遍历
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
//树的层级从1开始递归计数
traverse(pRoot, res, 1);
return res;
}
};
Python实现代码：
class Solution:
def traverse(self, root: TreeNode, res: List[List[int]], depth: int):
if root:
#数组长度小于当前层数，新开一层
if len(res) < depth:
res.append([])
#数组从0开始计数因此减1，在节点当前层的数组中插入节点
res[depth - 1].append(root.val)
#递归左右时节点深度记得加1
self.traverse(root.left, res, depth + 1);
self.traverse(root.right, res, depth + 1)
#层次遍历
def Print(self , pRoot: TreeNode) -> List[List[int]]:
res = []
#树的层级从1开始递归计数
self.traverse(pRoot, res, 1)
return res
复杂度分析：
- 时间复杂度：，其中为二叉树的节点数，每个节点访问一次
- 空间复杂度：，递归栈的最大深度为二叉树退化为链表时，深度为
