Given the root of a binary tree, flatten the tree into a “linked list”:
The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.
from leetcode_py import TreeNodeclass Solution: # Time: O(n), each node is visited a constant number of times # Space: O(1), pointers are rewired in place def flatten(self, root: TreeNode[int] | None) -> None: current = root while current is not None: if current.left is not None: predecessor = current.left while predecessor.right is not None: predecessor = predecessor.right predecessor.right = current.right current.right = current.left current.left = None current = current.right
