Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> st;
TreeNode* pre = nullptr, *cur = root;
while(cur || !st.empty()){
while(cur){
st.push(cur);
cur = cur->left;
}
cur = st.top();
// pop immediately to avoid repetitively visit
st.pop();
res.push_back(cur->val);
if(cur->right && cur->right != pre){
cur = cur->right;
//We need to continue for the next loop in order
//to get the most left nodes to stack
continue;
}
pre = cur;
cur = nullptr;
}
return res;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment