Simple Non-recursive solution


  • 0
    Q

    inspired by Morris traversal.

    void flatten(TreeNode* root) {
        while (root) {
            if (root->left) {
                TreeNode* t = root->left;
                while (t->right) {
                    t = t->right;
                }
                t->right = root->right;
    
                root->right = root->left;
                root->left = NULL;
            }
    
            root = root->right;
        }
    }
    

  • 0
    Q

    use stack to implement pre-order traversal, straight-forward solution.

    void flatten(TreeNode* root) {
        stack<TreeNode*> s;
        if (root) s.push(root);
    
        TreeNode dummy(0);
        TreeNode* tail = &dummy;
    
        while (!s.empty()) {
            TreeNode* now = s.top();
            s.pop();
    
            if(now->right) s.push(now->right);
            if(now->left) s.push(now->left);
    
            tail->right = now;
            tail->left = NULL;
            tail = tail->right;
        }
    }
    

Log in to reply
 

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