I'm trying to flatten a binary tree into a linked list.
I have a working, correct solution:
# Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def insert(root, node): if root.right is None: root.right = node return None else: insert(root.right, node) class Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ if root is None: return None if root.left is None and root.right is None: return root left = self.flatten(root.left) right = self.flatten(root.right) root.left = None if left: root.right = left insert(root.right, right) else: root.right = right return root
I'm not certain, but I think the time complexity is \$O(n^2)\$. How do I make it run faster? Specifically, how do I modify it so that it runs in optimal time complexity (linear time)?