LeetCode 430. Flatten a Multilevel Doubly Linked List

430. Flatten a Multilevel Doubly Linked List

solution 1

DFS traverse and put every nodes inorder to a list

then traverse the list and rebuild a single level linked list.

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:return None
        nodes = []
        def dfs(node):
            if node is None:return
            nodes.append(node)
            if node.child:dfs(node.child)
            if node.next:dfs(node.next)
        dfs(head)
        head = nodes[0]
        head.child=None
        for i in range(1, len(nodes)):
            node = nodes[i]
            prev = nodes[i-1]
            node.child=None
            node.prev=prev
            prev.next = node
        return head

C++ code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/
class Solution {
public:
    void helper(Node* node, vector<int>& nodes)
    {
        if (!node)return;
        nodes.push_back(node->val);
        if (node->child)helper(node->child, nodes);
        if (node->next)helper(node->next, nodes);
    }
    Node* flatten(Node* head) {
        if(!head)return head;
        vector<int> nodes;
        helper(head, nodes);
        auto node = new Node(nodes[0]);
        head = node;
        for (int i=1;i<nodes.size();++i)
        {   
            auto v = nodes[i];
            auto new_node = new Node(v);
            node->next = new_node;
            new_node->prev = node;
            node = new_node;
        }
        return head;
      
    }
};

Solution 2

change it into a preorder binary tree traversal problem: child is the left node and next is the right node

Image is from here

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:return None
        dummy = Node(-1, None, head, None)
        def dfs(prev, curr):
            if not curr:return prev
            curr.prev = prev
            prev.next = curr
            temp_next = curr.next
            tail = dfs(curr, curr.child)
            curr.child = None
            return dfs(tail, temp_next)            
        
        dfs(dummy, head)
        dummy.next.prev = None
        return dummy.next

solution 3

This is an iteration method.

Time complexity: O(n)

Space complexity: O(n)

class Solution:
    def flatten(self, head):
        if head is None:return None
        dummy = Node(-1, None, head, None)
        prev = dummy
        stack = [head]
        
        while stack:
            curr = stack.pop()
            
            prev.next = curr
            curr.prev = prev
            
            if curr.next:
                stack.append(curr.next)
            if curr.child:
                stack.append(curr.child)
                curr.child = None
            
            prev = curr
        dummy.next.prev = None
        return dummy.next

solution 4 recursion [1]

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/
class Solution {
public:
    Node* dfs(Node* node)
    {
        if (!node)return node;
        auto child = node->child;
        auto next = node->next;
        node->child = nullptr;
        if (child && next)
        {
            node->next = child;
            child->prev = node;
            
            auto end_child = dfs(child);
            auto end_next = dfs(next);
            
            end_child->next = next;
            next->prev = end_child;
            return end_next;
        }
        else if(child && !next)
        {
            node->next = child;
            child->prev = node;
            auto end_child = dfs(child);
            return end_child;
        }
        else if(!child && next)
        {
            auto end_next = dfs(next);
            return end_next;
        }
        else
        {
            // if no child and no next, return node itself.
            return node;
        }
    }
    Node* flatten(Node* head) 
    {
        dfs(head);
        return head;
    }
};

Reference

[1]https://youtu.be/Lf632zybIKY