二叉树前、中、后序遍历的递归、迭代实现

前序遍历

递归实现

vector<int> preorderTraversal(TreeNode* root) {if(!root)return {};vector<int> res;preorder(root,res);return res;      
}void preorder(TreeNode* root,vector<int> &res){if(!root)return;res.push_back(root->val);if(root->left)preorder(root->left,res);if(root->right)preorder(root->right,res);            
}

迭代实现

思路:先遍历到最左侧，并在遍历过程中将值依次存入到栈和返回的vector中，再依次从下部后入栈的数据中遍历右侧部分。

方法1

    vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(!root)return {};       stack<TreeNode*> s;findleft(root,res,s);while(!s.empty()){          TreeNode *tmp=s.top();s.pop();cout<<"s is "<<tmp->val;if(tmp->right){findleft(tmp->right,res,s);}       }return res;      } void findleft(TreeNode* root,vector<int> &res,stack<TreeNode*> &s){while(root){cout<<"root is "<<root->val;res.push_back(root->val);s.push(root);root=root->left;}}

方法2:与上述方法思路相同，表达不同

 vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(!root)return {};       stack<TreeNode*> s;TreeNode *tmp=root;while(tmp || !s.empty()){if(tmp){s.push(tmp);res.push_back(tmp->val);tmp=tmp->left;}else{tmp=s.top();s.pop();tmp=tmp->right;}}return res;      } 

中序遍历

递归实现

 vector<int> inorderTraversal(TreeNode* root) {vector<int>res;inorder(root,res);return res;                                                                                                         }                                                                                                                         void inorder(TreeNode* root,vector<int> &res){if(!root)return;if(root->left) inorder(root->left,res);  res.push_back(root->val);if(root->right)inorder(root->right,res);}

迭代实现 

方法1：从根结点开始从左依次入栈找到最左侧的叶结点，之后开始回退，回退时也找寻到有结点的最左侧，并依次入栈回退

vector<int> inorderTraversal(TreeNode *root) {vector<int> res;stack<TreeNode*> s;findleft(root,s);while(!s.empty()){TreeNode *cur=s.top();s.pop();res.push_back(cur->val);findleft(cur->right,s);}return res;}//遍历找到最左侧的叶子结点void findleft(TreeNode *root,stack<TreeNode*> &s){while(root){s.push(root);root=root->left;}}

方法2:与方法1思路相似，表达不同

    vector<int> inorderTraversal(TreeNode *root) {vector<int> res;stack<TreeNode*> s;TreeNode *cur=root;while(cur || !s.empty()){if(cur){s.push(cur);cur=cur->left;//判断是否有值并向左侧寻找}else{cur=s.top();s.pop();res.push_back(cur->val);cur=cur->right;//当左侧为空时，遍历右侧}}return res;}

后序遍历

递归方式：

 vector<int> postorderTraversal(TreeNode* root) {vector<int> res;if(!root)return {};postorder(root,res);return res;       }void postorder(TreeNode *root,vector<int> &res){if(root){if(root->left)postorder(root->left,res);if(root->right)postorder(root->right,res);res.push_back(root->val);}        }