LeetCode刷题实战156：上下翻转二叉树-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 上下翻转二叉树（这题Leetcode需要会员才能看），我们先来看题面：

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

Given a binary tree in which all right nodes are either leaf nodes with sibling nodes (left nodes with the same parent nodes) or empty, flip the binary tree up and down and turn it into a tree, and the original right nodes will be converted into left leaf nodes. Returns the new root.

题意

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

样例

解题

https://blog.csdn.net/qq_32424059/article/details/93920527

思路1：递归

对于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

思路2：迭代

对于任意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