0156._Binary_Tree_Upside_Down.md

156. Binary Tree Upside Down

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/binary-tree-upside-down/

内容描述

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.

Example:

Input: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1  
Clarification:

Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

对于每一个左节点l, 我们都要让l.left = parent, l.right = parent.right

所以我们可以把所以这些要改变的信息存到一个stack里面，最后逆序处理即可

class Solution:
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if not root.left and not root.right:
            return root
        
        stack, dummy = [], root
        while root:
            l, r = root.left, root.right
            if l:
                stack.append([l, r, root])
            root = l
        stack = stack[::-1]
        flag, res = False, -1
        for idx, (l, r, root) in enumerate(stack):
            if not flag:
                res = idx
            flag = True
            l.right = root
            l.left = r
        dummy.left, dummy.right = None, None
        return stack[res][0]

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

其实压根不需要把所有要改变的信息存下来，我们可以边往下走边改变

class Solution:
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        # take care of the root
        l, r = root.left, root.right
        root.left = root.right = None
        # update the left and the right children, form the new tree, update root
        while l:
            real_l, real_r = l.left, l.right
            l.left = r
            l.right = root
            root = l
            l, r = real_l, real_r
        return root