LeetCode: Binary Tree Upside Down Posted on February 11, 2018July 26, 2020 by braindenny Binary Tree Upside Down Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #binarytree, #recursive Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root. For example: Given a binary tree {1,2,3,4,5}, 1 / \ 2 3 / \ 4 5 return the root of the binary tree [4,5,2,#,#,3,1]. 4 / \ 5 2 / \ 3 1 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution ## https://code.dennyzhang.com/binary-tree-upside-down ## Basic Ideas: recursive post-order ## ## Complexity: Time O(n), Space O(1) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode: if (not root) or (not root.left): return root p = self.upsideDownBinaryTree(root.left) root.left.left = root.right root.left.right = root root.left, root.right = None, None return p ## https://code.dennyzhang.com/binary-tree-upside-down ## Basic Ideas: In-order ## ## Complexity: Time O(n), Space O(h). h = height of the tree # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def upsideDownBinaryTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if root is None: return None stack = [] p = root while p: stack.append(p) p = p.left newRoot = stack.pop(-1) q = newRoot while len(stack) != 0: pre_parent = stack.pop(-1) q.left = pre_parent.right q.right = pre_parent q = pre_parent # configure the last node as a leaf q.left, q.right = None, None return newRoot Post Views: 2