<reponame>Linchin/python_leetcode_git<gh_stars>0
"""
156
binary tree upside down
medium
"""


# 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 upsideDownBinaryTree(self, root):

        if not root:
            return None

        stack = []
        curr = root
        while curr is not None:
            stack.append(curr)
            curr = curr.left

        new_root = stack[-1]

        while len(stack) >= 2:
            curr = stack.pop()
            parent = stack[-1]
            curr.left = parent.right
            curr.right = parent

        stack[-1].left = None
        stack[-1].right = None

        return new_root


"""
156
binary tree upside down
medium
"""


# 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 upsideDownBinaryTree(self, root):

        if not root:
            return None

        stack = []
        curr = root
        while curr is not None:
            stack.append(curr)
            curr = curr.left

        new_root = stack[-1]

        while len(stack) >= 2:
            curr = stack.pop()
            parent = stack[-1]
            curr.left = parent.right
            curr.right = parent

        stack[-1].left = None
        stack[-1].right = None

        return new_root
156 binary tree upside down medium # Definition for a binary tree node.