二叉树的遍历

树	森林	二叉树
先序遍历	先序遍历	先序遍历
后序遍历	中序遍历	中序遍历

1.前序遍历

leetcode题目链接

1.1 递归

前序遍历递归方式

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root){res.push_back(root->val);vector<int> l = preorderTraversal(root->left);res.insert(res.end(),l.begin(),l.end());vector<int> r = preorderTraversal(root->right);res.insert(res.end(),r.begin(),r.end());}return res;}
};

1.2 非递归

前序遍历迭代方式一

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

前序遍历迭代方式二

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;while( root || s.size()){while(root){res.push_back(root->val);s.push(root);root = root->left;}root = s.top() , s.pop();root = root->right;}return res;}
};

2 中序遍历

leetcode题目链接

2.1 递归

中序遍历递归方式

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root){vector<int> l = inorderTraversal(root->left);res.insert(res.end(),l.begin(),l.end());res.push_back(root->val);vector<int> r = inorderTraversal(root->right);res.insert(res.end(),r.begin(),r.end());}return res;}
};

非递归

中序遍历迭代方式一

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;while(root || s.size()){if( root ){s.push(root);root = root->left;}else{root = s.top() , s.pop();res.push_back(root->val);root = root->right;}}return res;}
};

中序遍历迭代方式二

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;while(root || !s.empty()){while(root){s.push(root);root = root->left;}root = s.top() , s.pop();res.push_back(root->val);root = root->right;}return res;}
};

3 后序遍历

leetcode题目链接

3.1 递归

后序递归遍历方式

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;if(root){vector<int> l = postorderTraversal(root->left);res.insert(res.end(),l.begin(),l.end());vector<int> r = postorderTraversal(root->right);res.insert(res.end(),r.begin(),r.end());res.push_back(root->val);}return res;}
};

3.2 非递归

后序遍历迭代方式

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;TreeNode* pre = NULL;while(root || s.size()){if(root){s.push(root);root = root->left;}else{root = s.top();if(root->right && pre != root->right)root = root->right;else{s.pop();res.push_back(root->val);pre = root;root = NULL;}}}return res;}
};