N叉树问题-LeetCode 429、589、590、105、106（构建二叉树，N叉树遍历）
N叉树问题-LeetCode 429、589、590、105、106（构建二叉树，N叉树遍历）
作者：TeddyZhang，公众号：算法工程师之路
1
编程题
二叉树拓展到N叉树思路
- 先序中入栈顺序先右后左 --> 孩子节点数组从右向左入栈
- 后序中入栈顺序先左后右 --> 孩子节点数组从左向右入栈
【LeetCode #429】N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。(即从左到右，逐层遍历)。 例如，给定一个 3叉树 :
返回其层序遍历:
[ [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） 链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
【LeetCode #589】N叉树的前序遍历
给定一个 N 叉树，返回其节点值的前序遍历。 例如，给定一个 3叉树 :
返回其前序遍历: [1,3,5,6,2,4]。
/*
// 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） 链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
【LeetCode #590】N叉树的后序遍历
给定一个 N 叉树，返回其节点值的后序遍历。 例如，给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
/*
// 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） 链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
【LeetCode #105】从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。
例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
解题思路：
使用分治的思想，从一个节点开始递归的构建其左右子树，将一个问题分成多个子问题，这种递归的思路非常简单，下面代码边界也十分清晰！
由于preorder中的第一个元素必定为根节点，那么可以在inorder中去查找该节点（题中说元素不值重复）,找到之后得到索引 i, 根据中序遍历的性质，索引 i 的左边的数值为根节点的左子树的中序遍历，而对应到preorder中索引1到i+1为根节点的左子树的前序遍历！同理得到右子树的前序和中序遍历，那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树，即得到答案！
/**
* 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） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
【LeetCode #106】从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。
例如，给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
解题思路：
使用分治的思想，从一个节点开始递归的构建其左右子树，将一个问题分成多个子问题，这种递归的思路非常简单，下面代码边界也十分清晰！
由于postorder中的最后一个元素必定为根节点，那么可以在inorder中去查找该节点（题中说元素不值重复）,找到之后得到索引 i, 根据中序遍历的性质，索引 i 的左边的数值为根节点的左子树的中序遍历，而对应到postorder中索引 0 到 i 为根节点的左子树的前序遍历！同理得到右子树的后序和中序遍历，那么这样就变成了两个个子问题 --> 递归的构建根节点的左右子树，即得到答案！
/**
* 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;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal