Change the Root of a Binary Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def __init__(self):
        self.original_root = None

    def flipBinaryTree(self, root: 'Node', leaf: 'Node') -> 'Node':
        self.original_root = root
        return self.helper(leaf, None)  # the new parent of the leaf node must be None

    def helper(self, node, new_parent):
        old_parent = node.parent
        node.parent = new_parent

        if node.left == new_parent:
            node.left = None
        if node.right == new_parent:
            node.right = None

        if node == self.original_root:
            return node

        if node.left is not None:
            node.right = node.left
        node.left = self.helper(old_parent, node)

        return node