前序遍历,中序遍历,后序遍历的非递归方式及层序遍历(背诵)
leetcode 第144题,第94题,第145题,第102题
前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root==NULL) return ans;
TreeNode *stack[10000];
int top=-1;
TreeNode *p=root;
while(top!=-1||p){
if(p){
ans.push_back(p->val);
stack[++top] = p;
p=p->left;
}
else{
p = stack[top];
top--;
p=p->right;
}
}
return ans;
}
};
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
TreeNode *stack[100001];
int top=-1;
TreeNode *p = root;
while(top!=-1||p){
if(p){
stack[++top] = p;
p=p->left;
}
else{
p = stack[top];
top--;
ans.push_back(p->val);
p=p->right;
}
}
return ans;
}
};
后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
TreeNode *stack[100001];
int top=-1;
TreeNode *p = root;
while(top!=-1||p){
if(p){
ans.push_back(p->val);
stack[++top] = p;
p=p->right;
}
else{
p = stack[top];
top--;
p=p->left;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
TreeNode *q[10000];
int front=0,rear=0;
if(root==NULL) return ans;
q[rear++] = root;
while(front!=rear){
int len = rear-front;
vector<int> level;
for(int i=0;i<len;i++){
TreeNode *temp = q[front++];
if(temp->left!=NULL) q[rear++] = temp->left;
if(temp->right!=NULL) q[rear++] = temp->right;
level.push_back(temp->val);
}
ans.push_back(level);
}
return ans;
}
};