C++ O(n) in time and O(1) in space using Morris Traversal


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
TreeNode* predecessor(TreeNode* cur){
    if(cur->left == nullptr)
        return nullptr;
    TreeNode* pred = cur->left;
    while(pred->right != nullptr and pred->right != cur)
        pred = pred->right;
    return pred;
}
 
vector<int> Solution::inorderTraversal(TreeNode* A) {
    if(A == nullptr)
        return vector<int>();
    vector<int> ans;
    TreeNode* cur = A;
    while(cur != nullptr){
        if(cur->left == nullptr){
            ans.emplace_back(cur->val);
            cur = cur->right;
        }
        else{
            TreeNode* pred = predecessor(cur);
            if(pred->right == nullptr){
                pred->right = cur;
                cur = cur->left;
            }
            else{
                ans.emplace_back(cur->val);
                pred->right = nullptr;
                cur = cur->right;
            }
        }
    }
    return ans;
}