三个月算法进阶--day89

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <=3:
            return n-1
        a, b = n // 3, n % 3
        if b == 0:
            return int(math.pow(3, a))
        elif b == 1:
            return int(math.pow(3, a-1)) * 4
        else:
            return int(math.pow(3, a)) * 2

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def recur(left, right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return recur(left.left, right.right) and recur(left.right, right.left)
        
        if not root:
            return True
        return recur(root.left, root.right)

class Solution:
    def spiralOrder(self, matrix:[[int]]) -> [int]:
        if not matrix: return []
        l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
        while True:
            for i in range(l, r + 1): res.append(matrix[t][i]) # left to right
            t += 1
            if t > b: break
            for i in range(t, b + 1): res.append(matrix[i][r]) # top to bottom
            r -= 1
            if l > r: break
            for i in range(r, l - 1, -1): res.append(matrix[b][i]) # right to left
            b -= 1
            if t > b: break
            for i in range(b, t - 1, -1): res.append(matrix[i][l]) # bottom to top
            l += 1
            if l > r: break
        return res

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        ans, path = [], []
        def cur(node, target):
            if not node:
                return
            path.append(node.val)
            target -= node.val
            if target == 0 and not node.left and not node.right:
                ans.append(list(path))
            cur(node.left, target)
            cur(node.right, target)
            path.pop()
        cur(root, sum)
        return ans

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left) # 递归左子树
            if self.pre: # 修改节点引用
                self.pre.right, cur.left = cur, self.pre
            else: # 记录头节点
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

class Solution:
    def permutation(self, s: str) -> List[str]:
        if not s:
            return []
        s = list(s)
        ans = []
        def dfs(x):
            if x == len(s) - 1:
                ans.append(''.join(s))
                return
            dic = set()
            for i in range(x, len(s)):
                if s[i] in dic:
                    # 剪枝
                    continue
                s[i], s[x] = s[x], s[i]
                dic.add(s[x])
                dfs(x+1)
                s[i], s[x] = s[x], s[i]
        dfs(0)
        return ans