Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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
linkedin
github
slack

Post Views: 2
Posted in BasicTagged #binarytree, #recursive

Post navigation

LeetCode: Moving Average from Data Stream
LeetCode: Valid Word Square

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.