Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in vector which contains node values.
*/
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> output;
stack<TreeNode *> st;
while (root || !st.empty()){
if (!root) {
root = st.top();
st.pop();
output.push_back(root->val);
root = root->right;
}
else {
st.push(root);
root = root->left;
}
}
return output;
}
};
//Morris Traversal
vector<int> inorderTraversal(TreeNode *root) {
vector<int> output;
while(root) {
if (root->left) {
TreeNode *prev = root->left;
while(prev->right != NULL && prev->right != root)
prev = prev->right;
if (!prev->right) {
prev->right = root;
root =root->left;
}
else {
prev->right = NULL;
output.push_back(root->val);
root = root->right;
}
}
else {
output.push_back(root->val);
root = root->right;
}
}
return output;
}
class Solution {
void pushLeft(TreeNode *root, stack<TreeNode *> &st) {
while(root) {
st.push(root);
root = root->left;
}
}
class Solution {
void pushLeft(TreeNode *root, stack<TreeNode *> &st) {
while(root) {
st.push(root);
root = root->left;
}
}
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> output;
stack<TreeNode*> st;
pushLeft(root, st);
while (!st.empty()) {
root = st.top();
st.pop();
output.push_back(root->val);
pushLeft(root->right, st);
}
return output;
}
};
No comments:
Post a Comment