N叉树的遍历§
前序§
递归版
对于N叉树的前序遍历,首先读取数值,然后从左向右依次对所有孩子结点进行递归调用。
class Solution {
public:
void rec(Node* root, vector<int>& vpre){
if(!root) return;
vpre.emplace_back(root->val);
for(Node* p:root->children){
rec(p,vpre);
}
}
vector<int> preorder(Node* root){
vector<int> ans;
if(!root) return ans;
rec(root,ans);
return ans;
}
};
非递归
前序遍历的非递归方法需要借助栈。首先根结点入栈,然后进入循环,只要栈非空,访问栈顶结点并从右向左将其所有孩子结点逆序入栈,继续循环。
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> ans;
stack<Node*> ts;
if(root) ts.push(root);
while(!ts.empty()){
Node* p=ts.top();
ans.push_back(p->val);
ts.pop();
for(auto t=p->children.crbegin();t!=p->children.crend();++t){
ts.push(*t);
}
}
return ans;
}
};
后序§
递归版
先递归,再取数(值)。
class Solution {
public:
void rec(Node* root, vector<int> &vpost){
if(!root) return;
for(Node* p:root->children)
rec(p,vpost);
vpost.emplace_back(root->val);
}
vector<int> postorder(Node* root){
vector<int> ans;
if(!root) return ans;
rec(root,ans);
return ans;
}
};
非递归
这是一个有技巧的方法,先记录下来。首先根结点入栈,然后进入循环,只要栈非空,读取栈顶结点数值并从左向右依次将孩子结点入栈。这样的结果是,对任意子树,总是先获得根结点数值,再从右向左获得所有孩子结的值。因此反转获得的数值序列得到后序遍历结果。
class Solution {
public:
vector<int> postorder(Node* root){
vector<int> ans;
if(!root) return ans;
stack<Node*> ts;
ts.push(root);
while(!ts.empty()){
Node* p=ts.top();
ans.emplace_back(p->val);
ts.pop();
for(Node* t:p->children){
ts.push(t);
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
层序§
层序遍历需要借助队列实现。根结点入队后进入循环,首先取当前队列大小,表示一层中结点数,依次取数据并将所有孩子结点入队。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<Node*> q;
q.push(root);
while(!q.empty()){
int cnt=q.size();
vector<int> rec;
for(int i=0;i<cnt;++i){
Node* cur=q.front();
q.pop();
rec.emplace_back(cur->val);
for(Node* t:cur->children)
q.emplace(t);
}
ans.emplace_back(rec);
}
return ans;
}
};
二叉树的中序遍历§
递归版
class Solution {
public:
void rec(Node* root, vector<int> &vin){
if(!root) return;
rec(root->left,vin);
vin.emplace_back(root->val);
rec(root->right,vin);
}
vector<int> inorder(Node* root){
vector<int> ans;
if(!root) return ans;
rec(root,ans);
return ans;
}
};
非递归
两种方法。
第一种,首先迭代将左孩子入栈直到没有左孩子为止,然后进入循环,只要栈非空,取栈顶数据并出栈,每当结点有右孩子时,右孩子入栈并迭代将左孩子入栈。
第二种,以根结点为当前结点,只要栈非空或当前结点存在进行循环,循环中有两部分,第一部分迭代将当前结点的左孩子入栈,第二部分取栈顶数据并出栈,使得当前结点为栈顶结点的右孩子(无论右孩子是否存在)。
class Solution {
public:
vector<int> inorderTraversal1(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> ts;
ts.push(root);
while(root->left){
root=root->left;
ts.push(root);
}
while(!ts.empty()){
TreeNode* cur=ts.top();
ans.emplace_back(cur->val);
ts.pop();
if(cur->right){
TreeNode* t=cur->right;
ts.push(t);
while(t->left){
t=t->left;
ts.push(t);
}
}
}
return ans;
}
vector<int> inorderTraversal2(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> ts;
TreeNode* cur=root;
while(!ts.empty()||cur){
while(cur){
ts.push(cur);
cur=cur->left;
}
if(!ts.empty()){
cur=ts.top();
ans.emplace_back(cur->val);
ts.pop();
cur=cur->right;
}
}
return ans;
}
};