Intuitive O(n) C++ Solution Using a Queue (Combo of Iterative and Recursive)


  • 0
    V

    As the hint implies, use a pre-order traversal to visit every node; during each visit, add the node to a queue and delink the node from the graph. Once we're done with this, we simply step through each node we visited in order and link them like a chain.

    class Solution {
    public:
        std::queue<TreeNode *> myq;
    
        void PreOrder(TreeNode *root)
        {
            if (root == 0) return;
            myq.push(root);
            PreOrder(root->left);
            PreOrder(root->right);
            root->left = 0;
            root->right = 0;
        }
        void flatten(TreeNode* root) {
            if (root == 0) return;
            TreeNode *next = 0;
            PreOrder(root);
            while (!myq.empty())
            {
                if (next == 0)
                {
                    next = myq.front();
                    myq.pop();
                    continue;
                }
                next->right = myq.front();
                myq.pop();
                next = next->right;
            }
            
        }
    };
    

Log in to reply
 

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