156. Binary-Tree-Upside-Down.md

Description

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

---

强烈建议忽视这道题：

• like:dislike = 128:412, 直接反映出大家对这道题的评价是多么烂。
• 题意比较难懂，需要花大量时间理解。
• 就算做出来也没有什么成就感。。

解析：

转换过程如下图，1-3，2-4之间的连接被去掉，2-3，4-5之间增加了连接。

可以这样想像，转换后的树相当于把原来的树顺时针旋转了90度

上面的图只是表达了转换的过程，从转换结果上来看，是这样的：

                         Root                   L
                         /  \                  /  \
                        L    R                R   Root

我们以L(左子树)为基准，转换后，L的左子树为Root的右子树R，L的右子树为它的父节点Root。（把原来的树顺时针旋转90度，这样想就好理解多了）。

所以，可以使用循环（迭代）来重复上述过程：

# 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):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root

        l, r = root.left, root.right
        root.left, root.right = None, None   # 转换后原来根节点一定没有左子树和右子树，为什么呢？我们要把树顺时针旋转90度，而根节点的正右方是没有任何节点的，所以旋转90度后它的正下方也没有任何节点。

        while l:
            newL = l.left
            newR = l.right
            l.left = r    # L的左子树为Root的右子树R
            l.right = root   # L的右子树为它的父节点Root
            root = l         # 下次循环开始
            l = newL
            r = newR

        return root