[Python] DFS with stack, 2 solutions, exaplained
In this problem we need to traverse our multilevel doubly linked list in some special order and rebuild some connections. We can consider our list as graph, whi
In this problem we need to traverse our multilevel doubly linked list in some special order and rebuild some connections. We can consider our list as graph, which we now need to traverse. What graph traversal algorighms do we know? We should think about dfs and bfs. Why I choose dfs? Because we need to traverse as deep as possible, before we traverse neibhour nodes, and that is what dfs do exactly! When you realise this, problem becomes much more easier. So, algorighm look like:\n\n1. Put `head` of our list to stack and start to traverse it: `pop` element from it and add two two elements instead: its `next` and its `child`. The order is **important**: we first want to visit `child` and then `next`, that is why we put `child` to the top of our stack.\n2. Each time we `pop` last element from stack, I write it to auxilary `order` list.\n3. Last step is to rebuild from our `order` list flattened doubly linked list.\n\n**Complexity**: time complexity is `O(n)`, where `n` is number of nodes in our list. In this approach we also use `O(n)` additional space, because I keep `order` list. This can be avoid, if we make connections on the fly, but it is a bit less intuitive in my opinion, but ofcourse more optimal in space complexity.\n\n```\nclass Solution:\n    def flatten(self, head):\n        if not head: return head\n        stack, order = [head], []\n\n        while stack:\n            last = stack.pop()\n            order.append(last)\n            if last.next:\n                stack.append(last.next)\n            if last.child:\n                stack.append(last.child)\n        \n        for i in range(len(order) - 1):\n            order[i+1].prev = order[i]\n            order[i].next = order[i+1]\n            order[i].child = None\n            \n        return order[0]\n```\n\n**Solution without extra array**: the same idea, where we reconnect our nodes directly, without `order` array. It is `O(h)` in memory, where `h` is number of levels (in the worst case it will be `O(n)`).\n\n```\nclass Solution(object):\n    def flatten(self, head):\n        if not head: return head\n        \n        dummy = Node(0)\n        curr, stack = dummy, [head]\n        while stack:\n            last = stack.pop() \n            if last.next:\n                stack.append(last.next)\n            if last.child:\n                stack.append(last.child)\n            curr.next = last\n            last.prev = curr  \n            last.child = None\n            curr = last\n        \n        res = dummy.next\n        res.prev = None\n        return res\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']