Morris traversal


#1
vector<int> Solution::preorderTraversal(TreeNode* root) {
//morris traversal
TreeNode *current, *pre;
vector<int> v;
if (root == NULL)
    return v;

current = root;
while (current != NULL) {

    if (current->left == NULL) {
        v.push_back(current->val);
        current = current->right;
    }
    else {
        pre = current->left;
        while (pre->right != NULL
               && pre->right != current)
            pre = pre->right;


        if (pre->right == NULL) {
            pre->right = current;
            v.push_back(current->val);
            current = current->left;
        }

        else {
            pre->right = NULL;
            current = current->right;
        }
    } 
} 
return v;

}