LeetCode-Python-156. 上下翻转二叉树

给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空，将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。

例子:

输入: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

输出: 返回二叉树的根 [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1  
说明:

对 [4,5,2,#,#,3,1] 感到困惑? 下面详细介绍请查看 二叉树是如何被序列化的。

二叉树的序列化遵循层次遍历规则，当没有节点存在时，'#' 表示路径终止符。

这里有一个例子:

   1
  / \
 2   3
    /
   4
    \
     5
上面的二叉树则被序列化为 [1,2,3,#,#,4,#,#,5].

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-upside-down
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种思路：

递归， 对于root而言，root应该成为root.left的右孩子，root.right应该成为root.left的左孩子。

最后返回的是root.left处理之后的返回值。

class Solution(object):
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #每一个节点变成其左孩子的右节点        
        if not root or (not root.left and not root.right):
            return root

        newroot = self.upsideDownBinaryTree(root.left)
        # self.upsideDownBinaryTree(root.right) 右孩子不用处理 因为要么不存在要么是叶节点
        
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None

        return newroot

第二种思路：

迭代。

对于任意node，假设我们已经知道了它的父节点和兄弟节点，

先把node.left, node.right备份好，

然后node.left 就是兄弟节点， node.right就是父节点。

下一次循环处理备份好的原来的node.left。

class Solution(object):
    def upsideDownBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #每一个节点变成其左孩子的右节点        
        if not root or (not root.left and not root.right):
            return root

        parent, sibling = None, None
        while root:
            tmp = root.left
            root.left = sibling
            
            sibling = root.right
            root.right = parent
            
            parent = root
            root = tmp
            
        return parent