[Leetcode] 114. Flatten Binary Tree to Linked List (v hard)

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150

initial

I thought of swapping left subtre and right subtree but apparently its not the way to do this. I thought hard for like 40mins but i couldnt

solution

So first we have to find the rightmost child in the left subtree. That means the deepest right child in left subtree.
Then, we assign the current's right to p.right, which attaches the root's right subtree onto the right child of p pointer node. Then, we shif the entire root's left subtree to root's right subtree. We continue while current and current=current.right.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        current = root
        while current:
            if current.left:
                p=current.left
                while p.right!=None:
                    p=p.right
                p.right=current.right
                current.right=current.left
                current.left=None

            current=current.right
            
        

complexity

n time
1 space