114. Flatten Binary Tree to Linked List - cocoder39/coco39_LC GitHub Wiki

114. Flatten Binary Tree to Linked List

method 1: morris preorder traversal

         1 (cur)                     
        / \
       2   5
      / \   \
     3   4   6
       (tail)

         1                   
        / \
       #   2 (cur)
         /  \
        3    4
              \
               5
                \
                 6

O(n) time. similar with morris traversal. the while loop would go left then all the way right, hence each edge would only be visited once.

void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* tail = cur->left;
                while (tail->right) {
                    tail = tail->right;
                }
                tail->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }

Method 2: traversal order is right -> left -> root, which is reverse of preorder, thus pre of root is left, and pre of left is right. flattening tree from bottom to up

O(n) time and O(height) space

class Solution {
public:
    void flatten(TreeNode* root) {
        if (! root) {
            return;
        }
        
        flatten(root->right);
        flatten(root->left);
        root->right = pre;
        root->left = nullptr;
        pre = root;
    }
private:
    TreeNode* pre = nullptr;
};

solution 3: divide-and-queue

         1                      
        / \
       2   5
      / \   \
     3   4   6

         1                      
        / \
       2   5
        \   \
         3   6
          \
           4
        (tail)

we want to link tail (4) ->right to root->right (5), thus use helper() to return the tail of the flattened linked list. attention to corner case root, or root->left, or root->right is nullptr

class Solution {
public:
    void flatten(TreeNode* root) {
        helper(root);
    }
private:
    TreeNode* helper(TreeNode* root) {
        if (! root) return nullptr;
        
        TreeNode* leftTail = helper(root->left);
        TreeNode* rightTail = helper(root->right);
        
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        root->left = nullptr;
        if (left) {
            root->right = left;
            leftTail->right = right;
        }
        
        if (right) {
            return rightTail;
        } else if (left) {
            return leftTail;
        } else {
            return root;
        }
    }
};

follow up: flatten tree inorder

class Solution {
public:
    void flatten(TreeNode* root) {
        auto p = helper(root);
        auto node = p.first;
        while (node) {
            cout << node->val << " ";
            node = node->right;
        }
    }
private:
    pair<TreeNode*, TreeNode*> helper(TreeNode* root) {
        if (! root) return {nullptr, nullptr};
        
        auto left = helper(root->left);
        auto right = helper(root->right);
        
        if (left.second) {
            left.second->right = root;
        } 
        root->left = nullptr;
        root->right = right.first;
        
        TreeNode* head = left.first ? left.first : root;
        TreeNode* tail = right.second ? right.second : root;
        return {head, tail};
    }
};
⚠️ **GitHub.com Fallback** ⚠️