# Summary of Iterative Tree Traversal Solution & KMP

• Post-order

``````//post order iterative traversal
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
stack<TreeNode*> nodes;
TreeNode* pre = nullptr;
nodes.push(root);
while (!nodes.empty()) {
root = nodes.top();
if ((root->left == nullptr) && (root->right == nullptr) ||
(pre != nullptr && (root->left = pre || root->right == pre))) {
ans.push_back(root->val);
nodes.pop();
pre = root;
}
else {
if (root->right) nodes.push(root->right);
if (root->left) nodes.push(root->left);
}
}
}
``````

In-Order

``````//in order iterative traversal
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> nodes;
while (root || !nodes.empty()) {
while (root) {
nodes.push(root);
root = root->left;
}
if (!nodes.empty()) {
root = nodes.top();
nodes.pop();
ans.push_back(root->val);
root = root->right;
}
}
}
``````

Pre-Order

``````//pre order iterative traversal
vector<int> pre-orderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
root = nodes.top();
nodes.pop();
ans.push_back(root->val);
if (root->right) nodes.push(root->right);
if (root->left) nodes.push(root->left);
}
return ans;
}
``````

• Easy to grasp in-order solution

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

• ``````class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (!root) return result;
else st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
result.push_back(cur->val);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
return result;
}
};

``````

• Tricky Post-order Solution :

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(!root) return result;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
result.push_back(cur->val);
if (cur->left) st.push(cur->left);
if (cur->right) st.push(cur->right);
}
reverse(result.begin(), result.end());
return result;
}
};

``````

• Post Order Solution

``````class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> st;
TreeNode* pre = nullptr;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
if ((cur->left == nullptr) && (cur->right == nullptr) ||
(pre != nullptr && (cur->left == pre || cur->right == pre))) {
result.push_back(cur->val);
st.pop();
pre = cur;
}
else {
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
}
return result;
}
};

``````

• Important !!!
In fact, my classmates meet this problem when google onsite, but it requires that you can not use DFS and level by level BFS. So you should consider some traversal based solution to get the max depth of the binary tree.

Here is a concise implementation, you just can draw and run some cases and you will grasp it quickly !!!

``````
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
stack<TreeNode*> s;
s.push(root);
int result = 0;
TreeNode* prev = nullptr;
while (!s.empty()) {
TreeNode* cur = s.top();
if (!prev || prev->left == cur || prev->right == cur) {
if (cur->left) {
s.push(cur->left);
}
else if (cur->right) {
s.push(cur->right);
}
}
else if (cur->left == prev) {
if (cur->right)
s.push(cur->right);
} else {
s.pop();
}
prev = cur;
if (s.size() > result) {
result = s.size();
}
}
return result;
}
};``````

• KMP solution offered by fff

``````class Solution {
public:
vector<int> getNext(string needle) {
if (needle.size() == 0) return vector<int>();
vector<int> next(needle.size()+1);
int i = 0;
int j = -1;
next[i] = j;
while (i < needle.size()) {
while (j != -1&& needle[i]!=needle[j]) j = next[j];
next[++i] = ++j;
}
return next;
}
int strStr(string haystack, string needle) {
if (needle == "") return 0;
if (haystack == "") return -1;
if (needle.size() > haystack.size()) return -1;
vector<int> next = getNext(needle);
int i = 0;
int j = 0;
while (i < haystack.size()) {
while (j != -1 && haystack[i] != needle[j]) j = next[j];
i ++;
j ++;
if (j == needle.size()) {
return i - j;
}
}
return -1;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.