关于二叉树的前中后序遍历及中序遍
1.首先是前中后序遍历的递归写法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res ;
if(!root) return res ;
dfs(root, res) ;
return res ;
}
void dfs(TreeNode* root, vector<int>& res)
{
if(!root) return ;
res.push_back(root -> val) ;
dfs(root -> left, res) ;
dfs(root -> right, res) ;
}
};
2.接着是前后序的迭代写法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res ;
if(!root) return res ;
stack<TreeNode*> stk ;
stk.push(root) ;
while(!stk.empty())
{
auto node = stk.top() ;
stk.pop() ;
res.push_back(node -> val) ;
if(node -> right) stk.push(node -> right) ;
if(node -> left) stk.push(node -> left) ;
}
//reverse(res.begin(), res.end()) ; // 后序
return res ;
}
};
3.中序遍历的迭代写法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res ;
if(!root) return res ;
stack<TreeNode*> stk ;
while(root || stk.size())
{
while(root)
{
stk.push(root) ;
root = root -> left ;
}
root = stk.top() ;
stk.pop() ;
res.push_back(root -> val) ;
root = root -> right ;
}
return res ;
}
};
4.层序遍历的写法
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res ;
queue<TreeNode*> q ;
if(!root) return res ;
q.push(root) ;
while(q.size())
{
int size = q.size() ;
vector<int> level ;
for(int i = 0 ; i < size ; i ++)
{
auto node = q.front() ;
q.pop() ;
level.push_back(node -> val) ;
if(node -> left) q.push(node -> left) ;
if(node -> right) q.push(node -> right) ;
}
res.push_back(level) ;
}
return res ;
}
};