114.-flatten-binary-tree-to-linked-list.md

114. Flatten Binary Tree to Linked List

• Medium

• 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.

Analysis

Since we are asked to make all the next nodes to be on the right child, we can start by looking at the right child that is the most right: or so as to say, the last node to appear on the pre-order traversal.

When we look at that we saw that it doesn't have any right children anymore. So we can take it and move one step backward. This time add the node to it and link the right child with what we previously have.

	root
    / 
  1 
 / \ 
3  4  

Let's see what is happening with this code.

1. Node(4).right = None
2. Node(4).left = None
3. prev = Node(4)

---

1. Node(3).right = Node(4) (prev)
2. Node(3).left = None
3. prev = Node(3)->Node(4)

---

1. Node(1).right = prev = Node(3) -> Node(4)
2. Node(1).left = None
3. prev = Node(1)->Node(3)->Node(4) (Which is the answer)

---

• The answer use self.prev to recode the ordered tree of the right part of current node.
• Remove the left part of current node

class Solution:
    def __init__(self):
        self.prev=None
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return None 
        self.flatten(root.right)
        self.flatten(root.left)
        
        root.right=self.prev
        root.left=None
        self.prev=root