Problem statement

https://binarysearch.com/problems/Binary-Tree-to-Linked-List/

Solution

Variation of Leetcode 0114. Flatten Binary Tree to Linked List, but now we need to use different order: inorder instead of preorder

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        def helper(node):
            if not node: return (None, None)
            b1, e1 = helper(node.left)
            b2, e2 = helper(node.right)
            nodeL = LLNode(node.val)
            
            if not e1 and not e2:
                return (nodeL, nodeL)
            if not e1 and e2: 
                nodeL.next = b2
                return (nodeL, e2)
            if e1 and not e2:
                e1.next = nodeL
                return (b1, nodeL)
            else:
                e1.next = nodeL
                nodeL.next = b2
                return (b1, e2)

        return helper(root)[0]