1

思路：首先想到的就是暴力枚舉，不出所料超時(shí)了。然后就沒有思路了。查看官方解釋，發(fā)現(xiàn)歸并算法還有這個(gè)效果。兩個(gè)分別有序的子數(shù)組，在經(jīng)過歸并排序的過程中，每一步中如果是后面的元素比較小，則將后面的元素排序并統(tǒng)計(jì)前一個(gè)子數(shù)組中的剩余元素個(gè)數(shù)并累計(jì)。最后得到的就是逆序?qū)倲?shù)，并且還能得到排序后的有序數(shù)組。

時(shí)間復(fù)雜度是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

思路：這題是真的一點(diǎn)思路都沒有，題目都沒看懂。后來看完題解之后有了一點(diǎn)思路，可以用遞歸，先找到最左邊的左子節(jié)點(diǎn)，它就是最后的根節(jié)點(diǎn)然后從左下角，左子節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)，根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)，右節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)。

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