N叉树的广度优先遍历和深度优先遍历
class Node {
public:
int val;
vector<Node*> children;
};
// N 叉树的非递归层序遍历（广度优先遍历）
void levelOrderTraverse(Node* root) {
if (root == nullptr) {
return;
}
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
// 访问 cur 节点
std::cout << cur->val << std::endl;
// 把 cur 的所有子节点加入队列
for (Node* child : cur->children) {
q.push(child);
}
}
}
// N 叉树的递归先序遍历（深度优先遍历）
void Preorder(Node* root){
// 先序遍历
if(nullptr == root) return;
// 访问当前节点
cout << root->data << endl;
// 访问子节点
for(auto node:root->children){
Preorder(node);
}
}
// N 叉树的非递归先序遍历（深度优先遍历）
void preorder_stack(node* root){
if(nullptr == root) return;
stack<node*> s;
s.push(root);
while(!s.empty()){
node* node = s.top();
s.pop();
cout << node->data << " ";
for(int i=node->children.size()-1; i>=0; i--){
s.push(node->children[i]);
}
}
}
// N 叉树的递归后序遍历（深度优先遍历）
void Postorder(Node* root){
// 先序遍历
if(nullptr == root) return;
// 访问子节点
for(auto node:root->children){
Postorder(node);
}
// 访问当前节点
cout << root->data << endl;
}
// N 叉树的非递归后序遍历（深度优先遍历）
void Postorder_stack(Node* root){
if(nullptr == root) return;
stack<Node*> s;
s.push(root);
Node* pre = root;
while(!s.empty()){
Node* node = s.top();
if(node->children.empty() // 叶子结点
|| pre == node->children.back() // 分支节点的叶子节点完>成访问
){
s.pop();
cout << node->data << " ";
}else{
for(int i=node->children.size()-1; i>=0; i--){
s.push(node->children[i]);
}
}
pre = node;
}
}
// N 叉树的非递归层序遍历（广度优先遍历）
int depth(Node* root) {
if(nullptr == root) return 0;
int maxdepth = 0;
for(auto child : root->children){
maxdepth = max(maxdepth, depth(child));
}
return maxdepth+1;
}
void traverLayer(Node* root, int level){
if(nullptr == root) return;
if(level == 0){
cout << root->data << " ";
}else{
for(auto child:root->children){
traverLayer(child,level-1);
}
}
}
void BFS2(Node* root){
if(nullptr == root) return;
int n=depth(root);
for(int i=0; i<n; i++){
traverLayer(root, i);
}
}