递归遍历
遍历递归还是挺简单的。三道题都顺利的做出来了
迭代遍历
先做了前序遍历的迭代递归。我记得之前做的时候用了一个index来统计目前需要loop的次数，但是我试探着写出来之后，发现没用上。试着跑一下，结果没问题。看来还是基础不扎实，凭的多是记忆，而不是能力。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
if(root == nullptr){
return res;
}
st.push(root);
while(!st.empty()){
TreeNode* cur_node = st.top();
res.push_back(cur_node->val);
st.pop();
if(cur_node->right != nullptr){
st.push(cur_node->right);
}
if(cur_node->left != nullptr){
st.push(cur_node->left);
}
}
return res;
}
};
扫了一眼发现中序遍历比较复杂，所以就先做了后序遍历。后序遍历其实代码和前序差不多，稍改一点就行。但是我还是没自己改出来。看了Carl的题解，原来是改变先入栈的顺序，让输出完全反过来，然后再reserve。还是有点绕的。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
if(root == nullptr){
return res;
}
st.push(root);
while(!st.empty()){
TreeNode* cur_node = st.top();
res.push_back(cur_node->val);
st.pop();
if(cur_node->left != nullptr){
st.push(cur_node->left);
}
if(cur_node->right != nullptr){
st.push(cur_node->right);
}
}
reverse(res.begin(),res.end());
return res;
}
};
边看着Carl的解析便写出来的中序遍历，是有些难度。还需要重新做一遍。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
TreeNode* cur= root;
while(cur!=nullptr || !st.empty()){
if(cur!=nullptr){
st.push(cur);
cur=cur->left;
}
else{
cur=st.top();
st.pop();
res.push_back(cur->val);
cur=cur->right;
}
}
return res;
}
};
统一迭代
看了一下，发现不太好理解。以后再看吧~
