# N叉树问题-LeetCode 429、589、590、105、106（构建二叉树，N叉树遍历）

1

• 先序中入栈顺序先右后左 --> 孩子节点数组从右向左入栈
• 后序中入栈顺序先左后右 --> 孩子节点数组从左向右入栈

【LeetCode #429】N叉树的层序遍历

[ [1], [3,2,4], [5,6] ]

```/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
queue<Node*> que;
if(root == nullptr) return res;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
while(size--){
Node* tmp = que.front();
que.pop();
vec.push_back(tmp->val);
for(auto child: tmp->children){
if(child != nullptr){
que.push(child);
}
}
}
res.push_back(vec);
}
return res;
}
};
```

【LeetCode #589】N叉树的前序遍历

```/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> res;
if(root == nullptr)  return res;
stack<Node*> sta;
sta.push(root);
while(!sta.empty()){
Node* tmp = sta.top();
sta.pop();
res.push_back(tmp->val);
auto it = tmp->children.rbegin();
for(; it != tmp->children.rend(); it++){
if(*it != nullptr){
sta.push(*it);
}
}
}
return res;
}
};
```

【LeetCode #590】N叉树的后序遍历

```/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> postorder(Node* root) {
vector<int> res;
if(root == nullptr) return res;
stack<Node*> sta;
sta.push(root);
while(!sta.empty()){
Node* tmp = sta.top();
sta.pop();
res.insert(res.begin(), tmp->val);
for(auto node: tmp->children){
if(node != nullptr){
sta.push(node);
}
}
}
return res;
}
};
```

【LeetCode #105】从前序与中序遍历序列构造二叉树

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == )  return nullptr;
int i = ;
while(inorder[i] != preorder[]){   // 找到中序遍历树根的位置
i++;
}
TreeNode* root = new TreeNode(preorder[]);
// 注意去除第一个preorder[0]
vector<int> preleft(preorder.begin()+, preorder.begin()+i+);   //左子树的preorder
vector<int> preright(preorder.begin()+i+, preorder.end());      //右子树的preorder
vector<int> inleft(inorder.begin(), inorder.begin()+i);          //左子树的inorder
vector<int> inright(inorder.begin()+i+, inorder.end());         //右子树的inorder
root->left = buildTree(preleft, inleft);
root->right = buildTree(preright, inright);
return root;
}
};
```

【LeetCode #106】从中序与后序遍历序列构造二叉树

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size() == )  return nullptr;
int n = postorder.size() - , i = ;
while(inorder[i] != postorder[n]){
i++;
}
TreeNode* root = new TreeNode(postorder[n]);
vector<int> inleft(inorder.begin(), inorder.begin()+i);         //左子树的inorder
vector<int> inright(inorder.begin()+i+, inorder.end());        //右子树的inorder
vector<int> postleft(postorder.begin(), postorder.begin()+i);   //左子树的postorder
vector<int> postright(postorder.begin()+i, postorder.end()-1);  //右子树的postorder
root->left = buildTree(inleft, postleft);
root->right = buildTree(inright, postright);
return root;
}
};
```

0 条评论

## 相关文章

8620

### 小白也能看懂的Pandas实操演示教程(上)

pandas中有两类非常重要的数据结构，就是序列Series和数据框DataFrame.Series类似于NumPy中的一维数组，可以使用一维数组的可用函数和方...

7240

10220

15710

### 干货 | 27 个问题，告诉你 Python 为什么如此设计？

https://docs.python.org/zh-cn/3.7/faq/design.html

5810

### 造轮子了！NETCore跨平台UI框架，CPF

CPF(暂时命名)（Cross platform framework），模仿WPF的框架，支持NETCore的跨平台UI框架，暂时不够完善，只用于测试，暂时只支...

6510

### 是否注意过isEmpty 和 isBlank 区别？

org.apache.commons.lang.StringUtils 类提供了 String 的常用操作,最为常用的判空有如下两种 isEmpty(Strin...

6330

### ​.NET手撸2048小游戏

2048是一款益智小游戏，得益于其规则简单，又和 2的倍数有关，因此广为人知，特别是广受程序员的喜爱。

13130

6120

10330