按层遍历二叉树

时间:2022-07-05 19:27:26
有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。

给定二叉树的根结点root,请返回打印结果,结果按照每一层一个数组进行储存,
所有数组的顺序按照层数从上往下,且每一层的数组内元素按照从左往右排列。

保证结点数小于等于500。

方法一:不使用队列,使用两个类型为TreeNode的vector容器Node,child
分别用于存放父结点层和其孩子结点的一层的所有接结点
1,遍历Node,当Node中的结点遍历完后,将其得到所有结点的值所在的vector容器num存放至result容器中,
并将Node与num容器都清空,此后的Node将用于child中所有结点的孩子结点(即用于存放下下层的结点)
2,遍历child,对其执行类似步骤1的操作(清空child后,child也将用于存放下下层的结点)

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :val(x), left(NULL), right(NULL){}
};
class TreePrinter
{
public:
vector<vector<int>>printTree(TreeNode *root)
{
vector<vector<int>>resullt;
vector<int>num;
vector<TreeNode*>Node;
vector<TreeNode*>child;
TreeNode *pNode = root;
Node.push_back(pNode);
while (Node.size()>0||child.size()>0)
{

for (int i = 0; i < Node.size(); i++)
{
num.push_back(Node[i]->val);
if (Node[i]->left)
child.push_back(Node[i]->left);
if (Node[i]->right)
child.push_back(Node[i]->right);
}
if (num.size()>0)
resullt.push_back(num);
num.clear();
Node.clear();
for (int j = 0; j < child.size();j++)
{
num.push_back(child[j]->val);
if(child[j]->left)
Node.push_back(child[j]->left);
if(child[j]->right)
Node.push_back(child[j]->right);
}
if (num.size()>0)
resullt.push_back(num);
num.clear();
child.clear();

}
return resullt;
}
};
/*
方法二:使用队列存放结点,使用nlast,last两个标志,last指向每一层的最右边的结点,
nlast指向队列中当前遍历结点的孩子结点,当当前遍历结点与last相等,则当前所在层的结点遍历完毕,last指向nlast(即下一层的最右边结点)
*/

vector<vector<int>>printTree(TreeNode *root)
{
vector<vector<int>>resullt;
vector<int>num;
queue<TreeNode*>Node;

TreeNode *last, *nlast, *temp;
Node.push(root);
last = root;
nlast = NULL;
while (!Node.empty())
{
temp = Node.front();
Node.pop();
num.push_back(temp->val);
if (temp->left)
{
Node.push(temp->left);
nlast = temp->left;
}
if (temp->right)
{
Node.push(temp->right);
nlast = temp->right;
}
if (last == temp)
{
last = nlast;
resullt.push_back(num);
num.clear();
}

}
return resullt;
}