236题105题46题47题

第一题、236.二叉树的最近公共祖先

方法一、递归
递归遍历整棵二叉树，定义 fx 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：(flson&& frson) ∣∣ ((x = p ∣∣ x = q) && (flson∣∣ frson)) ，其中 lson 和 rson 分别代表 x 节点的左孩子和右孩子。
flson && frson：说明左子树和右子树均包含 p 节点或 q 节点，如果左子树包含的是 p 节点，那么右子树只能包含 q 节点，反之亦然，因为 p 节点和 q 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 x 就是要找的最近公共祖先。
((x = p ∣∣ x = q) && (flson∣∣ frson))：这个判断条件即是考虑了 x 恰好是 p 节点或 q 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 x 就是要找的最近公共祖先。
按上述判断条件找出来的公共祖先深度是否是最大的？：
是最大的，因为是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 fx 本身的定义很巧妙，在找到最近公共祖先 x 以后，fx 按定义被设置为 true ，即假定了这个子树中只有一个 p 节点或 q 节点，因此其他公共祖先不会再被判断为符合条件。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.ans = None

    def dfs(self, root, p, q):
        # 如果当前节点为空，返回False
        if root is None:
            return False
        # 递归遍历左子树
        lson = self.dfs(root.left, p, q)
        # 递归遍历右子树
        rson = self.dfs(root.right, p, q)
        # 如果左子树和右子树都找到了目标节点，或者当前节点是目标节点之一且在其左右子树中找到了另一个目标节点
        if (lson and rson) or ((root.val == p.val or root.val == q.val) and (lson or rson)):
            # 当前节点就是公共祖先
            self.ans = root
        # 返回当前节点是否是目标节点之一或者其左右子树中是否找到了目标节点
        return lson or rson or (root.val == p.val or root.val == q.val)

    def lowestCommonAncestor(self, root, p, q):
        # 调用dfs函数进行深度优先搜索
        self.dfs(root, p, q)
        # 返回找到的最近公共祖先节点
        return self.ans
用时和内存

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

（模拟有难度！建议多模拟几次复习）示例详解：要找到节点5和1的最近公共祖先。

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
  1. 从根节点（3）开始调用dfs函数。
    • root.val = 3，ans = None
  2. 递归遍历左子树（根节点5）。
    • root.val = 5，ans = None
    • 继续递归遍历左子树（根节点6）。
      • root.val = 6，ans = None
      • 左子树为空，返回False。
      • 右子树为空，返回False。
      • 节点6不是目标节点，返回False。
    • lson = False
    • 递归遍历右子树（根节点2）。
      • root.val = 2，ans = None
      • 继续递归遍历左子树（根节点7）。
        • root.val = 7，ans = None
        • 左子树为空，返回False。
        • 右子树为空，返回False。
        • 节点7不是目标节点，返回False。
      • lson = False
      • 继续递归遍历右子树（根节点4）。
        • root.val = 4，ans = None
        • 左子树为空，返回False。
        • 右子树为空，返回False。
        • 节点4不是目标节点，返回False。
      • rson = False
      • 节点2不是目标节点，返回False。
    • rson = False
    • 节点5是目标节点，返回True。
    • lson = True
  3. 递归遍历右子树（根节点1）。
    • root.val = 1，ans = None
    • 继续递归遍历左子树（根节点0）。
      • root.val = 0，ans = None
      • 左子树为空，返回False。
      • 右子树为空，返回False。
      • 节点0不是目标节点，返回False。
    • lson = False
    • 继续递归遍历右子树（根节点8）。
      • root.val = 8，ans = None
      • 左子树为空，返回False。
      • 右子树为空，返回False。
      • 节点8不是目标节点，返回False。
    • rson = False
    • 节点1是目标节点，返回True。
    • rson = True
  4. 回到根节点3，左子树返回True（找到节点5），右子树返回True（找到节点1）。
    • root.val = 3，lson = True，rson = True
    • 因为在根节点3处，左子树和右子树都找到了目标节点，根节点3即为最近公共祖先。
    • ans = root = 3
      最终输出的最近公共祖先节点值为3。

方法二、存储父节点
用哈希表存储所有节点的父节点，然后利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是要找的最近公共祖先。
算法实现：
从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

class Solution(object):
    def __init__(self):
        self.fa = {}  # 用于存储每个节点的父节点
        self.vis = {}  # 用于记录访问过的节点

    def dfs(self, root):
        # 如果左子节点不为空，记录左子节点的父节点为当前节点，并递归遍历左子树
        if root.left is not None:
            self.fa[root.left.val] = root
            self.dfs(root.left)
        # 如果右子节点不为空，记录右子节点的父节点为当前节点，并递归遍历右子树
        if root.right is not None:
            self.fa[root.right.val] = root
            self.dfs(root.right)

    def lowestCommonAncestor(self, root, p, q):
        self.fa[root.val] = None  # 根节点的父节点设为None
        self.dfs(root)  # 进行深度优先搜索以填充父节点信息
        
        # 遍历从节点p到根节点的路径，记录所有节点
        while p is not None:
            self.vis[p.val] = True
            p = self.fa[p.val]
        
        # 遍历从节点q到根节点的路径，第一个访问过的节点即为最近公共祖先
        while q is not None:
            if self.vis.get(q.val, False): # 使用get方法获取q.val对应的访问状态，如果不存在，返回False
                return q
            q = self.fa[q.val]
        
        return None  # 如果没有找到公共祖先，返回None
用时和内存

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。
空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度，因此最后总的空间复杂度为 O(N)。

示例详解

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
  1. 从根节点（3）开始，调用dfs函数。
    • fa = {3: None}
    • 遍历左子树（根节点5）。
      • fa = {3: None, 5: root}
      • 遍历左子树（根节点6）。
        • fa = {3: None, 5: root, 6: node5}
      • 遍历右子树（根节点2）。
        • fa = {3: None, 5: root, 6: node5, 2: node5}
        • 遍历左子树（根节点7）。
          • fa = {3: None, 5: root, 6: node5, 2: node5, 7: node2}
        • 遍历右子树（根节点4）。
          • fa = {3: None, 5: root, 6: node5, 2: node5, 7: node2, 4: node2}
    • 遍历右子树（根节点1）。
      • fa = {3: None, 5: root, 6: node5, 2: node5, 7: node2, 4: node2, 1: root}
      • 遍历左子树（根节点0）。
        • fa = {3: None, 5: root, 6: node5, 2: node5, 7: node2, 4: node2, 1: root, 0: node1}
      • 遍历右子树（根节点8）。
        • fa = {3: None, 5: root, 6: node5, 2: node5, 7: node2, 4: node2, 1: root, 0: node1, 8: node1}
  2. 遍历从节点5到根节点的路径，记录访问过的节点。
    • p = node5，vis = {5: True}
    • p = root，vis = {5: True, 3: True}
    • p = None
  3. 遍历从节点1到根节点的路径，第一个访问过的节点即为最近公共祖先。
    • q = node1
    • q = root，vis[3] = True，找到最近公共祖先3。
      最终输出的最近公共祖先节点值为3。

get()?:
在Python中，get是字典的一个方法，用于获取指定键的值。如果键不存在，则返回一个默认值（默认是None）。这个方法在访问字典中的值时非常有用，因为它可以避免直接访问不存在的键时抛出的KeyError异常。
在上述代码中

  1. self.vis.get(q.val, False)：尝试从字典self.vis中获取键q.val的值。如果键q.val存在，则返回其对应的值。如果键q.val不存在，则返回False。
  2. 如果vis[q.val]为True，说明节点q在遍历p的路径中已经访问过，那么当前的节点q即为最近的公共祖先，返回q。
  3. 如果没有找到，继续遍历节点q的父节点，直到找到最近公共祖先或遍历到根节点。

第二题、105. 从前序与中序遍历序列构造二叉树

方法一、递归
只要在中序遍历中定位到根节点，那么就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度是相同的，因此就可以对应到前序遍历的结果中。知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，就可以递归地构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。可以使用哈希表来快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，可以对中序遍历的列表进行一遍扫描，构造出哈希映射。在此后构造二叉树的过程中，只需要 O(1) 的时间即可对根节点进行定位。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # 内部函数用于递归构建树
        def myBuildTree(preorder_left, preorder_right, inorder_left, inorder_right):
            # 如果前序遍历的左边界大于右边界，说明子树为空
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点的位置
            inorder_root = index[preorder[preorder_root]]
            
            # 创建根节点
            root = TreeNode(preorder[preorder_root])
            # 计算左子树节点数目
            size_left_subtree = inorder_root - inorder_left
            
            # 递归构造左子树，并连接到根节点
            # 前序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            
            # 递归构造右子树
            # 前序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        
        # 获取前序遍历序列的长度
        n = len(preorder)
        # 构造哈希映射，帮助快速定位中序遍历中的根节点位置
        index = {element: i for i, element in enumerate(inorder)}
        # 调用递归函数构建树
        return myBuildTree(0, n - 1, 0, n - 1)
用时和内存

时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

示例详解：

  • 前序遍历：[3, 9, 20, 15, 7]
  • 中序遍历：[9, 3, 15, 20, 7]
  1. 初始化和预处理： 
    n = len(preorder)  # n = 5
index = {element: i for i, element in enumerate(inorder)}  # index = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}
  2. 调用递归函数myBuildTree(0, 4, 0, 4)开始构建树：
    1. 根节点为3（前序遍历的第一个元素），在中序遍历中位置为1，左子树大小为1： 
      root = TreeNode(3)
root.left = myBuildTree(1, 1, 0, 0)  # 构建左子树
root.right = myBuildTree(2, 4, 2, 4)  # 构建右子树
    2. 构建左子树myBuildTree(1, 1, 0, 0)：
      1. 根节点为9，在中序遍历中位置为0，左子树大小为0： 
        root = TreeNode(9)
root.left = myBuildTree(2, 1, 0, -1)  # 递归调用返回None
root.right = myBuildTree(2, 1, 1, 0)  # 递归调用返回None
    3. 构建右子树myBuildTree(2, 4, 2, 4)：
      1. 根节点为20，在中序遍历中位置为3，左子树大小为1： 
        root = TreeNode(20)
root.left = myBuildTree(3, 3, 2, 2)  # 构建左子树
root.right = myBuildTree(4, 4, 4, 4)  # 构建右子树
      2. 构建左子树myBuildTree(3, 3, 2, 2)：
        1. 根节点为15，在中序遍历中位置为2，左子树大小为0： 
          root = TreeNode(15)
root.left = myBuildTree(4, 3, 2, 1)  # 递归调用返回None
root.right = myBuildTree(4, 3, 3, 2)  # 递归调用返回None
      3. 构建右子树myBuildTree(4, 4, 4, 4)：
        1. 根节点为7，在中序遍历中位置为4，左子树大小为0： 
          root = TreeNode(7)
root.left = myBuildTree(5, 4, 4, 3)  # 递归调用返回None
root.right = myBuildTree(5, 4, 5, 4)  # 递归调用返回None

最终构建的二叉树为：

        3
       / \
      9   20
         /  \
        15   7

方法二、迭代（难）
对于前序遍历中的任意两个连续节点 u 和 v，可知 u 和 v 只有两种可能的关系：

  1. v 是 u 的左儿子：在遍历到 u 之后，下一个遍历的节点就是 u 的左儿子，即 v。
  2. u 没有左儿子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右儿子：如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。如果 u 没有右儿子，就会向上回溯，直到遇到第一个有右儿子（且 u 不在它的右儿子的子树中）的节点 ua ，那么 v 就是 ua 的右儿子。
    例子：
        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4
  • preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
  • inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
    用一个栈 stack 来维护「当前节点的所有还没有考虑过右儿子的祖先节点」，栈顶就是当前节点。也就是说，只有在栈中的节点才可能连接一个新的右儿子。同时，用一个指针 index 指向中序遍历的某个位置，初始值为 0。index 对应的节点是「当前节点不断往左走达到的最终节点」，这也是符合中序遍历的，它的作用在下面的过程中会有所体现。
    首先将根节点 3 入栈，再初始化 index 所指向的节点为 4，随后对于前序遍历中的每个节点，依次判断它是栈顶节点的左儿子，还是栈中某个节点的右儿子。
    具体步骤
  1. 遍历 9：9 一定是栈顶节点 3 的左儿子。反证法，假设 9 是 3 的右儿子，那么 3 没有左儿子，index 应该恰好指向 3，但实际上为 4，因此产生了矛盾。所以将 9 作为 3 的左儿子，并将 9 入栈。 
    stack = [3, 9]
index -> inorder[0] = 4
  2. 遍历 8，5 和 4：同理可得它们都是上一个节点（栈顶节点）的左儿子，所以它们会依次入栈。 
    stack = [3, 9, 8, 5, 4]
index -> inorder[0] = 4
  3. 遍历 10：这时情况就不一样了。index 恰好指向当前的栈顶节点 4，也就是说 4 没有左儿子，那么 10 必须为栈中某个节点的右儿子。栈中的节点的顺序和它们在前序遍历中出现的顺序是一致的，而且每一个节点的右儿子都还没有被遍历过，那么这些节点的顺序和它们在中序遍历中出现的顺序一定是相反的。因此可以把 index 不断向右移动，并与栈顶节点进行比较。如果 index 对应的元素恰好等于栈顶节点，那么说明在中序遍历中找到了栈顶节点，所以将 index 增加 1 并弹出栈顶节点，直到 index 对应的元素不等于栈顶节点。按照这样的过程，弹出的最后一个节点 x 就是 10 的双亲节点，这是因为 10 出现在了 x 与 x 在栈中的下一个节点的中序遍历之间，因此 10 就是 x 的右儿子。
    例子中依次从栈顶弹出 4，5 和 8，并且将 index 向右移动了三次。将 10 作为最后弹出的节点 8 的右儿子，并将 10 入栈。 
    stack = [3, 9, 10]
index -> inorder[3] = 10
  4. 遍历 20：同理，index 恰好指向当前栈顶节点 10，那么会依次从栈顶弹出 10，9 和 3，并且将 index 向右移动了三次。将 20 作为最后弹出的节点 3 的右儿子，并将 20 入栈。 
    stack = [20]
index -> inorder[6] = 15
  5. 遍历 15：将 15 作为栈顶节点 20 的左儿子，并将 15 入栈。 
    stack = [20, 15]
index -> inorder[6] = 15
  6. 遍历 7：index 恰好指向当前栈顶节点 15，那么会依次从栈顶弹出 15 和 20，并且将 index 向右移动了两次。将 7 作为最后弹出的节点 20 的右儿子，并将 7 入栈。 
    stack = [7]
index -> inorder[8] = 7

此时遍历结束，构造出了正确的二叉树。
算法流程：

  1. 用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点。
  2. 依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，将当前节点作为栈顶节点的左儿子。
  3. 无论是哪一种情况，最后都将当前的节点入栈。
    最后得到的二叉树即为答案。
class Solution(object):
    def buildTree(self, preorder, inorder):
        # 如果前序遍历为空，直接返回None
        if not preorder:
            return None

        # 前序遍历的第一个元素是根节点
        root = TreeNode(preorder[0])
        # 用栈来模拟树的构建过程
        stack = [root]
        inorderIndex = 0

        # 遍历前序遍历的剩余元素
        for i in range(1, len(preorder)):
            preorderVal = preorder[i]
            node = stack[-1]  # 获取栈顶节点
            # 如果栈顶节点值不等于当前中序遍历中的节点值，说明该节点是左子节点
            if node.val != inorder[inorderIndex]:
                node.left = TreeNode(preorderVal)
                stack.append(node.left)
            else:
                # 如果栈顶节点值等于当前中序遍历中的节点值，说明该节点没有左子节点或左子节点已处理完毕
                while stack and stack[-1].val == inorder[inorderIndex]:
                    node = stack.pop()
                    inorderIndex += 1
                # 将当前节点作为右子节点
                node.right = TreeNode(preorderVal)
                stack.append(node.right)

        return root
用时和内存

时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，返回答案需要 O(n) 空间， O(h)（其中 h 是树的高度）的空间存储栈。这里 h<n，所以（在最坏情况下）总空间复杂度为 O(n)。

示例详解：

  • 前序遍历：[3, 9, 20, 15, 7]
  • 中序遍历：[9, 3, 15, 20, 7]
  1. 初始化和预处理： 
    root = TreeNode(preorder[0])  # root = TreeNode(3)
stack = [root]  # stack = [TreeNode(3)]
inorderIndex = 0
  2. 遍历前序遍历的剩余元素：
    1. 处理节点9：
      • preorderVal = 9
      • 栈顶节点3的值不等于当前中序遍历中的节点值9： 
        node.left = TreeNode(9)  # TreeNode(3).left = TreeNode(9)
stack.append(node.left)  # stack = [TreeNode(3), TreeNode(9)]
    2. 处理节点20：
      • preorderVal = 20
      • 栈顶节点9的值等于当前中序遍历中的节点值9： 
        while stack and stack[-1].val == inorder[inorderIndex]:
    node = stack.pop()  # node = stack.pop() -> TreeNode(9)
    inorderIndex += 1  # inorderIndex = 1
node.right = TreeNode(20)  # TreeNode(3).right = TreeNode(20)
stack.append(node.right)  # stack = [TreeNode(3), TreeNode(20)]
    3. 处理节点15：
      • preorderVal = 15
      • 栈顶节点20的值不等于当前中序遍历中的节点值15： 
        node.left = TreeNode(15)  # TreeNode(20).left = TreeNode(15)
stack.append(node.left)  # stack = [TreeNode(3), TreeNode(20), TreeNode(15)]
    4. 处理节点7：
      • preorderVal = 7
      • 栈顶节点15的值等于当前中序遍历中的节点值15： 
        while stack and stack[-1].val == inorder[inorderIndex]:
    node = stack.pop()  # node = stack.pop() -> TreeNode(15)
    inorderIndex += 1  # inorderIndex = 2
while stack and stack[-1].val == inorder[inorderIndex]:
    node = stack.pop()  # node = stack.pop() -> TreeNode(20)
    inorderIndex += 1  # inorderIndex = 3
node.right = TreeNode(7)  # TreeNode(20).right = TreeNode(7)
stack.append(node.right)  # stack = [TreeNode(3), TreeNode(7)]

最终构建的二叉树为：

        3
       / \
      9   20
         /  \
        15   7

第三题、46.全排列

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。
回溯法生成全排列可以看作有n个排列成一行的空格，需要从左往右依次填入题目给定的n个数，每个数只能使用一次。
定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。整个递归函数分为两种情况：

  1. 递归终止条件：
    • 如果 first == n，说明已经填完了n个位置（注意下标从 0 开始），找到了一个可行的解，将 output 放入答案数组中，递归结束。
  2. 递归展开：
    • 如果 first < n，要考虑第 first 个位置填哪个数。根据题目要求，不能填已经填过的数。可以通过标记数组 vis 来标记已经填过的数。在填第 first 个数时，遍历题目给定的n个数，如果这个数没有被标记过，就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。回溯时要撤销这个位置填的数以及标记，并继续尝试其他没被标记过的数。
      优化方法：
      使用标记数组来处理填过的数是一个直观的思路，但可以优化，减少空间复杂度。可以将题目给定的n个数的数组 nums 划分成左右两个部分，左边表示已经填过的数，右边表示待填的数。在回溯时动态维护这个数组。
      具体来说，假设已经填到第 first 个位置，那么 nums 数组中 [0, first-1] 是已填过的数的集合，[first, n-1] 是待填的数的集合。尝试用 [first, n-1] 里的数去填第 first 个数。假设待填的数的下标为 i，那么填完后将第 i 个数和第 first 个数交换，使得在填第 first+1 个数时，nums 数组的 [0, first] 部分为已填过的数，[first+1, n-1] 为待填的数。回溯时交换回来即能完成撤销操作。
      示例：
      假设有 [2, 5, 8, 9, 10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8, 9] 两个数，那么这个数组目前为 [8, 9 | 2, 5, 10] 这样的状态，分隔符区分了左右两个部分。假设这个位置要填 10 这个数，为了维护数组，将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10 | 2, 5]。
      生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，可以使用标记数组或者其他方法。
      first 表示下一个待填入的位置
      i 是一个循环变量，用于遍历数组中的每个元素
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first):
            # 递归终止条件，所有数都填完了
            if first == n:
                res.append(nums[:])
                return
            for i in range(first, n):
                # 交换元素，动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 递归调用，继续递归填下一个数
                backtrack(first + 1)
                # 撤销交换
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack(0)
        return res
运行时间和内存

时空复杂度分析

示例详解：
123
初始状态

  • 数组 nums = [1, 2, 3]
  • 初始调用 backtrack(0)
    步骤 1: 填第 0 个位置
  1. first = 0，nums = [1, 2, 3]：
    • 尝试填第 0 个位置的每个可能的数。
    • i = 0，交换 nums[0] 和 nums[0]（保持不变）：[1, 2, 3]
      • 递归调用 backtrack(1)。
        步骤 2: 填第 1 个位置
  2. first = 1，nums = [1, 2, 3]：
    • 尝试填第 1 个位置的每个可能的数。
    • i = 1，交换 nums[1] 和 nums[1]（保持不变）：[1, 2, 3]
      • 递归调用 backtrack(2)。
        步骤 3: 填第 2 个位置
  3. first = 2，nums = [1, 2, 3]：
    • 尝试填第 2 个位置的每个可能的数。
    • i = 2，交换 nums[2] 和 nums[2]（保持不变）：[1, 2, 3]
      • 递归调用 backtrack(3)。
        步骤 4: 终止条件
  4. first = 3（终止条件）：数组已填满，当前排列是 [1, 2, 3]。
    • 结果集加入 output = [1, 2, 3]。
    • 回溯到 first = 2，撤销交换（无变化），继续尝试其他可能的排列。
      回溯到 first = 2，nums = [1, 2, 3]：
  5. 回溯到 first = 1，继续尝试 i = 2：
    • i = 2，交换 nums[1] 和 nums[2]：[1, 3, 2]
      • 递归调用 backtrack(2)。
        步骤 5: 填第 2 个位置
  6. first = 2，nums = [1, 3, 2]：
    • 尝试填第 2 个位置的每个可能的数。
    • i = 2，交换 nums[2] 和 nums[2]（保持不变）：[1, 3, 2]
      • 递归调用 backtrack(3)。
        步骤 6: 终止条件
  7. first = 3（终止条件）：数组已填满，当前排列是 [1, 3, 2]。
    • 结果集加入 output = [1, 3, 2]。
    • 回溯到 first = 2，撤销交换（无变化），继续回溯到 first = 1。
      回溯到 first = 1，nums = [1, 3, 2]：
  8. 回溯到 first = 0，撤销交换：[1, 2, 3]。
  9. 继续尝试 i = 1：
    • i = 1，交换 nums[0] 和 nums[1]：[2, 1, 3]
      • 递归调用 backtrack(1).
        步骤 7: 填第 1 个位置
  10. first = 1，nums = [2, 1, 3]：
    • 尝试填第 1 个位置的每个可能的数。
    • i = 1，交换 nums[1] 和 nums[1]（保持不变）：[2, 1, 3]
      • 递归调用 backtrack(2).
        步骤 8: 填第 2 个位置
  11. first = 2，nums = [2, 1, 3]：
    • 尝试填第 2 个位置的每个可能的数。
    • i = 2，交换 nums[2] 和 nums[2]（保持不变）：[2, 1, 3]
      • 递归调用 backtrack(3).
        步骤 9: 终止条件
  12. first = 3（终止条件）：数组已填满，当前排列是 [2, 1, 3]。
    • 结果集加入 output = [2, 1, 3]。
    • 回溯到 first = 2，撤销交换（无变化），继续回溯到 first = 1。
      回溯到 first = 1，nums = [2, 1, 3]：
  13. 回溯到 first = 0，继续尝试 i = 2：
    • i = 2，交换 nums[0] 和 nums[2]：[3, 2, 1]
      • 递归调用 backtrack(1).
        步骤 10: 填第 1 个位置
  14. first = 1，nums = [3, 2, 1]：
    • 尝试填第 1 个位置的每个可能的数。
    • i = 1，交换 nums[1] 和 nums[1]（保持不变）：[3, 2, 1]
      • 递归调用 backtrack(2).
        步骤 11: 填第 2 个位置
  15. first = 2，nums = [3, 2, 1]：
    • 尝试填第 2 个位置的每个可能的数。
    • i = 2，交换 nums[2] 和 nums[2]（保持不变）：[3, 2, 1]
      • 递归调用 backtrack(3).
        步骤 12: 终止条件
  16. first = 3（终止条件）：数组已填满，当前排列是 [3, 2, 1]。
    • 结果集加入 output = [3, 2, 1]。
    • 回溯到 first = 2，撤销交换（无变化），继续回溯到 first = 1。
      回溯到 first = 1，nums = [3, 2, 1]：
  17. 回溯到 first = 0，撤销交换：[1, 2, 3]。
    通过以上步骤，最终结果集为：
  18. [1, 2, 3]
  19. [1, 3, 2]
  20. [2, 1, 3]
  21. [2, 3, 1]
  22. [3, 1, 2]
  23. [3, 2, 1]
    图示

第四题、47.全排列2

方法、搜索回溯
此题是「46. 全排列」的进阶，序列中包含了重复的数字，要求返回不重复的全排列。整体回溯法思路同上。
但46题并没有满足此题「全排列不重复」的要求，在上述的递归函数中会生成大量重复的排列，因为对于第 first 的位置，如果存在重复的数字 i，算法每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复。
解决办法是保证在填第 first 个数的时候重复数字只会被填入一次。因此在本题中，需要对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue;
}

这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。
假设有 3 个重复数排完序后相邻，那么一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入] 到 [填入，未填入，未填入]，再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的过程的，因此可以达到去重的目标。

class Solution(object):
    def __init__(self):
        # 初始化一个标记列表，用于记录某个数是否被访问过
        self.vis = []

    def backtrack(self, nums, ans, idx, perm):
        # 如果当前排列的长度等于输入数组的长度，说明找到了一个完整的排列
        if idx == len(nums):
            ans.append(list(perm))
            return
        
        # 遍历所有数字
        for i in range(len(nums)):
            # 如果当前数字已经被访问过，或者当前数字和前一个数字相同且前一个数字未被访问过，跳过
            if self.vis[i] or (i > 0 and nums[i] == nums[i - 1] and not self.vis[i - 1]):
                continue

            # 选择当前数字，标记为已访问
            perm.append(nums[i])
            self.vis[i] = 1

            # 递归调用
            self.backtrack(nums, ans, idx + 1, perm)

            # 回溯，撤销选择
            self.vis[i] = 0
            perm.pop()

    def permuteUnique(self, nums):
        ans = []
        perm = []
        self.vis = [0] * len(nums)  # 初始化标记列表为未访问状态
        nums.sort()  # 对输入数组进行排序，便于去重
        self.backtrack(nums, ans, 0, perm)
        return ans

PS:此代码中的idx相当于46的first


用时和内存

时间复杂度分析同46题
空间复杂度：标记数组O(n) ，递归时栈深度 O(n)，因此总空间复杂度为 O(n+n)=O(2n)=O(n)。

示例详解：
以 [1, 1, 2] 为例：
初始调用：

  • nums = [1, 1, 2]
  • 排序后：nums = [1, 1, 2]
  • 初始化 vis = [0, 0, 0]
  • ans = []
  • perm = []
    第一层递归调用 (idx=0, perm=[]):
  1. i=0，选择第一个1：
    • perm = [1]
    • vis = [1, 0, 0]
    • 递归调用 backtrack(nums, ans, 1, perm)
      第二层递归调用 (idx=1, perm=[1]):
  2. i=0，第一个1已访问，跳过
  3. i=1，选择第二个1：
    • perm = [1, 1]
    • vis = [1, 1, 0]
    • 递归调用 backtrack(nums, ans, 2, perm)
      第三层递归调用 (idx=2, perm=[1, 1]):
  4. i=0 和 i=1 都已访问，跳过
  5. i=2，选择2：
    • perm = [1, 1, 2]
    • vis = [1, 1, 1]
    • 找到一个完整排列，加入 ans：ans = [[1, 1, 2]]
    • 回溯，撤销选择：
      • perm = [1, 1]
      • vis = [1, 1, 0]
        回溯到第二层 (idx=1, perm=[1]):
  6. 回溯：
    • 撤销选择第二个1：
      • perm = [1]
      • vis = [1, 0, 0]
  7. i=2，选择2：
    • perm = [1, 2]
    • vis = [1, 0, 1]
    • 递归调用 backtrack(nums, ans, 2, perm)
      第三层递归调用 (idx=2, perm=[1, 2]):
  8. i=0，选择第一个1：
    • perm = [1, 2, 1]
    • vis = [1, 1, 1]
    • 找到一个完整排列，加入 ans：ans = [[1, 1, 2], [1, 2, 1]]
    • 回溯，撤销选择：
      • perm = [1, 2]
      • vis = [1, 0, 1]
        回溯到第二层 (idx=1, perm=[1]):
  9. 回溯：
    • 撤销选择2：
      • perm = [1]
      • vis = [1, 0, 0]
        回溯到第一层 (idx=0, perm=[]):
  10. 回溯：
    • 撤销选择第一个1：
      • perm = []
      • vis = [0, 0, 0]
  11. i=1，选择第二个1，但因为它和前一个1相同且前一个1未被访问过，跳过
  12. i=2，选择2：
    • perm = [2]
    • vis = [0, 0, 1]
    • 递归调用 backtrack(nums, ans, 1, perm)
      第二层递归调用 (idx=1, perm=[2]):
  13. i=0，选择第一个1：
    • perm = [2, 1]
    • vis = [1, 0, 1]
    • 递归调用 backtrack(nums, ans, 2, perm)
      第三层递归调用 (idx=2, perm=[2, 1]):
  14. i=0，第一个1已访问，跳过
  15. i=1，选择第二个1：
    • perm = [2, 1, 1]
    • vis = [1, 1, 1]
    • 找到一个完整排列，加入 ans：ans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
    • 回溯，撤销选择：
      • perm = [2, 1]
      • vis = [1, 0, 1]
        回溯到第二层 (idx=1, perm=[2]):
  16. 回溯：
    • 撤销选择第一个1：
      • perm = [2]
      • vis = [0, 0, 1]
  17. i=1，选择第二个1，但它和前一个1相同且前一个1未被访问过，跳过
  18. i=2，2已访问，跳过
    回溯到第一层 (idx=0, perm=[]):
  19. 回溯：
    • 撤销选择2：
      • perm = []
      • vis = [0, 0, 0]
        最终，所有唯一的排列已经找到，结果为：
  • ans = [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,590评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,808评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,151评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,779评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,773评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,656评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,022评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,678评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,038评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,756评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,411评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,005评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,973评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,053评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,495评论 2赞 343

推荐阅读更多精彩内容