1

思路：首先想到的就是暴力枚举，不出所料超时了。然后就没有思路了。查看官方解释，发现归并算法还有这个效果。两个分别有序的子数组，在经过归并排序的过程中，每一步中如果是后面的元素比较小，则将后面的元素排序并统计前一个子数组中的剩余元素个数并累计。最后得到的就是逆序对总数，并且还能得到排序后的有序数组。

时间复杂度是O(n*logn)

class Solution:
    def __init__(self):
        self.count = 0

    def merge(self,nums1,nums2):
        nums3 = []
        while nums1 and nums2:
            if nums1[0] <= nums2[0]:
                nums3.append(nums1.pop(0))
            else:
                nums3.append(nums2.pop(0))
                self.count += len(nums1)
        if nums1:
            nums3 += nums1
        if nums2:
            nums3 += nums2
        return nums3

    def merge_sort(self,nums3):
        if len(nums3) <= 1:
                return nums3
        else:
            nums1 = nums3[:len(nums3) // 2]
            nums2 = nums3[len(nums3) // 2:]
            nums1 = self.merge_sort(nums1)
            nums2 = self.merge_sort(nums2)
            nums3 = self.merge(nums1,nums2)
            return nums3

    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        else:
            self.merge_sort(nums)
            return self.count

2

思路：这题是真的一点思路都没有，题目都没看懂。后来看完题解之后有了一点思路，可以用递归，先找到最左边的左子节点，它就是最后的根节点然后从左下角，左子节点变为根节点，根节点变为右子节点，右节点变为左子节点。

class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        if root is None or root.left is None and root.right is None:
            return root
        
        newroot = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root

        root.left = None
        root.right = None

        return newroot