114. Flatten Binary Tree to Linked List

class Solution 
{
private:
	TreeNode *iter; // we use iter to traverse the tree, for the tree, it means the last constructed node

    void preorderConstructTree(TreeNode *m_root) // we construct the tree like preorder traversal
    {
        auto rightSubTree = m_root->right; // we will turn all left nodes into right nodes, so we keep the right subtree for later use
        
        iter->right = m_root; // turn the current node into a right node
        iter = iter->right;
        
        // turn the left subtree
        if(iter->left) preorderConstructTree(iter->left); 
        // now, iter is the last node at the left subtree, then we link it with the origin right subtree
        if(rightSubTree) preorderConstructTree(rightSubTree); 
        
        // don't forget to delete all left subtrees
        m_root->left = nullptr;
    }
public:
    // void flatten(TreeNode* root)
    void flatten(TreeNode *m_root) 
    {
        if(!m_root) return;
        
        iter = new TreeNode();
        preorderConstructTree(m_root);
    }
};

class Solution 
{
public:
    // void flatten(TreeNode* root)
    void flatten(TreeNode *m_root) 
    {
        for(auto iter = m_root; iter; )
        {
            // if the iter->left is valid, then its most right node is the previous node of iter's right subtree
            if(iter->left) 
            {
                auto nextNode = iter->left;
                auto previousNode = nextNode;
                
                // we find the right subtree's previous node
                while(previousNode->right) previousNode = previousNode->right;

                // then link them
                previousNode->right = iter->right;
                iter->left = nullptr;
                iter->right = nextNode;
            }
            
            iter = iter->right;
        }
    }
};