10.30：二叉树-二叉搜索树的搜索、二叉搜索树的验证（二叉搜索树相关）

题目1-二叉搜索树的搜索：
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

分析：

题目本身非常简单，毕竟二叉搜索树就是为了搜索而生的嘛，只是要通过这一题复习一下二叉搜索树的定义：

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

显然，这是一个递归定义。

答案：

1.递归法（推荐）

public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }

2.迭代法

public TreeNode searchBST(TreeNode root, int val) {
        while (root != null)
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        return null;
    }

题目2-验证二叉搜索树（较难，可以多体会体会）：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

分析：

中序遍历下输出的二叉搜索树序列是一个递增的有序序列！有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

同时，注意一个问题：不能单纯的比较 左节点小于中间节点，右节点大于中间节点 就完事了，我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点，所以中序遍历的就会变得非常方便合理。

答案：

class Solution {
    // pre 用来保存上一次遍历到的节点
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
       // 空树也是二叉搜索树
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);         
      // 中
        if (pre != null && root.val <= pre.val) {
            return false;
        }
        pre = root;
        // 右
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

11.4：二叉树-二叉搜索树的最小绝对差（二叉搜索树巩固）

题目：

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。树中至少有 2 个节点。

分析：

注意是二叉搜索树，中序遍历下的二叉搜索树是有序的。遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

同时，要学会在递归遍历的过程中记录前后两个指针，这也是一个小技巧，学会了还是很受用的。

答案：

class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }
    public void traversal(TreeNode root){
        if(root==null)return;
        //左
        traversal(root.left);
        //中
        if(pre!=null){
            result = Math.min(result,root.val-pre.val);
        }
        pre = root;
        //右
        traversal(root.right);
    }
}

11.5：二叉树-二叉搜索树中的众数（再次强调二叉搜索树的特殊点）

题目：

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

分析：

首先，我们分析一下普通二叉树的解法。如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用 map 统计频率，把频率排个序，最后取前面高频的元素的集合。

接着，我们来看一下二叉搜索树的解法。如果是二叉搜索树，那他的中序遍历就是有序的。遍历有序数组的元素出现频率，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出。此时我们就需要弄一个指针 pre 指向前一个节点，这样每次 cur（当前节点）才能和 pre（前一个节点）作比较，而且初始化的时候 pre = null ，这样当 pre 为 null 的时候，我们就知道这是比较的第一个元素。

此时又有问题了，因为要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），所以应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合，这种方式遍历了两遍数组。

但其实可以只遍历一遍：当 频率count 等于 最大频率maxCount 的时候，把这个元素加入到结果集中；而当 count 大于 maxCount 的时候，不仅更新 maxCount ，而且要清空结果集，这样真正结果集之前的元素就都失效了。

答案：

11.6：二叉树-二叉树的最近公共祖先、二叉搜索树的最近公共祖先（寻找公共祖先）

题目1-二叉树的最近公共祖先：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

说明：

• 最近公共祖先节点可以为节点本身。
• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

分析：

找公共祖先，第一反应肯定是想要自下而上查找，自下而上查找就是回溯的过程，而二叉树的后序遍历（左右中）就是天然的回溯过程！这个时候就可以根据左右子树的返回值，来处理中节点的逻辑。那么这道题的判断逻辑就是：如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。这里注意一下，公共祖先就是节点本身的情况也是被包含在内的。
于是，我们来理清递归三部曲：

• 确定递归函数返回值以及参数
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
• 确定终止条件
  if (root == q || root == p || root == NULL) return root;
• 确定单层递归逻辑
  这里，必须要强调一下 搜索一条边 和 搜索整个树 的区别。
  • 搜索一条边：
    if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
  • 搜索整棵树：
    left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理; 
  • 区别：在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回；如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
  • 如果left 和 right都不为空，此时root作为最近公共节点返回。如果left为空，right不为空，此时right作为目标节点返回，反之依然。
    if(left == null && right == null) {
    return null;
}else if(left == null && right != null) {
    return right;
}else if(left != null && right == null) {
    return left;
}else {
    return root;
}

答案：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { // 递归结束条件
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }

题目2-二叉搜索树的最近公共祖先：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

分析：

显然，这题和上题最大的区别就是二叉搜索树，而二叉搜索树最大的特性之一就是其有序性，利用其有序性，我们可以发现：如果中间节点是 q 和 p 的公共祖先，那么中间节点的数组一定是在 [p, q]区间的。同时，我们通过找规律和逻辑推理可以发现：当我们从上向下去递归遍历，第一次遇到的数值在[q, p]区间中的节点，就是q和p的最近公共祖先。而递归遍历顺序，本题就不涉及到前中后序了（因为这里没有中节点的处理逻辑，只是普通遍历，所以遍历顺序无所谓了）。现在我们就可以用递归三部曲规划思路，完成算法了。注意：这里的单层递归逻辑完全可以使用上一题分析的 搜索一条边 的方法。

答案：

1. 递归法
   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    return root;
}
2. 迭代法（最简单明了的一集）
   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (true) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else {
            break;
        }
    }
    return root;
}

11.8、11.10：二叉树-二叉搜索树的插入 与 删除（重难点在删除操作上）

题目1-二叉搜索树的插入：

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

分析：

这题不难，只要利用好二叉搜索树的特性，按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。关键一点的是递归三部曲中的 确定递归函数参数以及返回值 这一步，有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作，具体情况看代码逻辑即可。同时，迭代法用到了之前重点提到过的记录 pre 和 cur 两个指针的操作。

答案：

1. 递归法：
   

   public TreeNode insertIntoBST(TreeNode root, int val) {
           if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
               return new TreeNode(val);
               
           if (root.val < val){
               root.right = insertIntoBST(root.right, val); // 递归创建右子树
           }else if (root.val > val){
               root.left = insertIntoBST(root.left, val); // 递归创建左子树
           }
           return root;
       }

2. 迭代法：
   

   public TreeNode insertIntoBST(TreeNode root, int val) {
           if (root == null) return new TreeNode(val);
           TreeNode newRoot = root;
           TreeNode pre = root;
           while (root != null) {
               pre = root;
               if (root.val > val) {
                   root = root.left;
               } else if (root.val < val) {
                   root = root.right;
               } 
           }
           if (pre.val > val) {
               pre.left = new TreeNode(val);
           } else {
               pre.right = new TreeNode(val);
           }
   
           return newRoot;
       }

题目2-二叉搜索树的删除：

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

分析：

递归三部曲：

1. 确定递归函数参数以及返回值-TreeNode deleteNode(TreeNode root, int key)
2. 确定终止条件-if (root == null) return root;
3. 确定单层递归的逻辑：二叉搜索树在删除节点时一共有以下五种情况：

• • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
  • 

关键点就在这五种情况，确认好这五种情况后，代码实现就变得简单了。

同时，我们也可以使用上一题强调的接住返回值的方法。

答案：

class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}

11.11：二叉树-修剪二叉搜索树、将有序数组转换为平衡二叉搜索树

题目1-修剪二叉搜索树：

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。

分析：

这道题有两个关键点：1. 即使某个节点满足了边界条件，它的左右孩子不一定满足。所以，要遍历整棵树。2. 当某个节点在边界之外，要去它的左右子树上寻找符合条件的头结点进行“嫁接”。

理清楚这两点以后就可以用递归三部曲实现代码了：

1. 确定递归函数的参数以及返回值：TreeNode trimBST(TreeNode root, int low, int high);
2. 确定终止条件：if (root == null) return null;
3. 确定单层递归的逻辑：如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。接下来将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。最后返回root节点。

答案：

1.递归法：

public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // root在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

2.迭代法：

public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null)
            return null;
        while(root != null && (root.val < low || root.val > high)){
            if(root.val < low)
                root = root.right;
            else
                root = root.left;
        }

        TreeNode cur = root;
        
        while(cur != null){
            while(cur.left != null && cur.left.val < low){
                cur.left = cur.left.right;
            }
            cur = cur.left;
        }

        cur = root;

        while(cur != null){
            while(cur.right != null && cur.right.val > high){
                cur.right = cur.right.left;
            }
            cur = cur.right;
        }
        return root;
    }

题目2-将有序数组转换为平衡二叉搜索树（二分法）：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

分析：

不要被题目唬到，这题其实很简单。因为这是个有序数组，有序想到什么？二分法啊！只需要用二分法每次取中间值，自然而然就能构造出平衡二叉搜索树了。所以这道题的本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。但是记得注意在二分法时着重强调的：循环不变量原则！

递归三部曲：

1. 确定递归函数返回值及其参数：TreeNode traversal(int[] nums, int left, int right) // 左闭右闭
2. 确定递归终止条件：if (left > right) return null;
3. 确定单层递归的逻辑：以中间位置的元素构造节点，接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。
   int mid = left + ((right - left) / 2);
TreeNode root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;

答案：

11.12：二叉树-把二叉搜索树转换为累加树

题目：

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

分析：

这题题干稍微有点难懂，其实就是让某个节点把树中所有大于等于它的节点值加到自己身上来。这个题初看会觉得有点麻烦，但一定要记得：中序遍历下的二叉搜索树是一个有序数组！这道题其实就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。对于二叉搜索树来说，操作它和操作这样一个数组是一样的。

那么现在再来看这个题。显然，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。而所谓的反中序也不过是换一下递归顺序而已。结合递归三部曲即可轻松解出。

答案：

11.14:回溯算法-组合问题+优化

题目：

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

回溯算法：

首先，我们来了解一下回溯算法是什么。回溯法也可以叫做回溯搜索法，它是一种搜索方式，我们之前已经在二叉搜索树中使用过多次。回溯是递归的副产品，只要有递归就会有回溯。回溯算法的性能并不好，因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

回溯算法模版：

• 回溯函数模板返回值以及参数：void backtracking(参数)（回溯算法中函数返回值一般为void，名字一般叫backtracking）
• 回溯函数终止条件：
  if (终止条件) {
存放结果;
return;
}
• 回溯搜索的遍历过程：
  
  
  
  for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
  for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历。

分析：

本题是回溯法的经典题目。直接的解法是使用for循环，例如示例中k为2，很容易想到用两个for循环：（如果k = 3，就用三个for循环）

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

但是，如果n为100，k为50呢？那就50层for循环。而且你无法使用硬编码的方式在测试前事先写好for循环的层数。所以很快就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来。此时就需要使用回溯搜索法了。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

现在我们来把组合问题抽象为如下树形结构：

可以看出这棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

图中每次搜索到了叶子节点，我们就找到了一个结果。

现在开始回溯三部曲：

1. 递归函数的返回值以及参数：

定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。

再定义一个int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历。

void backtracking(int n, int k, int startIndex)

2. 回溯函数终止条件

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

3. 单层搜索的过程

for循环每次从startIndex开始遍历，然后用path保存取到的节点i。

for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){ // 控制树的横向遍历
path.add(i); // 处理节点
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.removeLast(); // 回溯，撤销处理的节点
}

剪枝优化：

对于上方的遍历代码，是可以剪枝优化的。

举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。

显然，图中每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环条件所选择的位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为：k – path.size();
3. 在集合n中最多能从该起始位置： n – (k – path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n – (k – 0) + 1 即 4 – ( 3 – 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。（这里的优化过程有点难懂，多去理解一下）

所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)

答案：

未剪枝优化：

class Solution {
    List<List<Integer>> result= new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }

    public void backtracking(int n,int k,int startIndex){
        if (path.size() == k){
            // 深拷贝和浅拷贝
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i =startIndex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

剪枝优化：

11.15：回溯算法-组合总和III

题目：

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。

分析：

显然，这又是一道典型的组合问题，对比上一题，只不过加了一个总和的限制而已。上一题如果弄懂了，这一题就没什么难度。但是还是要注意一些细节。

答案：

class Solution {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> path = new LinkedList<>();

	public List<List<Integer>> combinationSum3(int k, int n) {
		backTracking(n, k, 1, 0);
		return result;
	}

	private void backTracking(int targetSum, int k, int startIndex, int sum) {
		// 减枝
		if (sum > targetSum) {
			return;
		}

		if (path.size() == k) {
			if (sum == targetSum) result.add(new ArrayList<>(path));
			return;
		}

		// 减枝 9 - (k - path.size()) + 1
		for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
			path.add(i);
			sum += i;
			backTracking(targetSum, k, i + 1, sum);
			//回溯
			path.removeLast();
			//回溯
			sum -= i;
		}
	}
}

11.19：回溯算法-电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

• 输入：”23″
• 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

分析：

显然，这是一个组合问题，组合问题就该用回溯算法解决。

回溯三部曲：

1. 确定回溯函数参数：
   List<String> list = new ArrayList<>();
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void backTracking(String digits, String[] numString, int num)
2. 确定终止条件
   if (num == digits.length()) {
  list.add(temp.toString());
  return;
}
3. 确定单层遍历逻辑
   String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
  temp.append(str.charAt(i));
  // 递归，处理下一层
  backTracking(digits, numString, num + 1);
  // 回溯
  temp.deleteCharAt(temp.length() - 1);
}
   注意这里for循环，可不是从startIndex开始遍历的。因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而之前的题目都是求同一个集合中的组合。

答案：

class Solution {

    //设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //迭代处理
        backTracking(digits, numString, 0);
        return list;

    }

    // 每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    StringBuilder temp = new StringBuilder();

    // 比如digits如果为"23",num为0，则str表示2对应的abc
    public void backTracking(String digits, String[] numString, int num) {
        // 遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        // str表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            // 递归，处理下一层
            backTracking(digits, numString, num + 1);
            // 回溯
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

11.20：回溯算法-组合总和

题目：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取，且所有数字（包括 target）都是正整数，但是解集不能包含重复的组合。

分析：

显然，这又是个组合问题，但是要注意一点，解集中不能有重复元素，而且本质上还是一个集合来求组合，所以还是需要startIndex。

对于组合问题，什么时候需要startIndex呢？

• 如果是一个集合来求组合的话，就需要startIndex。
• 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex。

明白这一点后，用回溯三部曲即可解答本题。

关于剪枝优化，这一题本来是在每一层递归的开始进行终止条件的判断的，也就是说，当 sum 明显大于 target 时，还需要将该 sum 传入下一层递归里判断后再返回。所以剪枝优化的思路是将 sum 大于 target 的判断放在本层递归中进行，这样就可以避免多余的递归。

答案：

11.21：回溯算法-组合总和II

题目：

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

• 示例 1:
• 输入: candidates = [10,1,2,7,6,1,5], target = 8,
• 所求解集为:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

• 示例 2:
• 输入: candidates = [2,5,2,1,2], target = 5,
• 所求解集为:

[
  [1,2,2],
  [5]
]

分析：

本题相对于 组合总和I 的难点是：数组candidates 有重复元素，但解集中不能有重复的组合。既然不能重复，那显然我们就必须做去重工作了。这道题如果先把所有组合求出来，再用set或map去重，会超时。所以要在搜索的过程中就去掉重复组合。

这道题的去重要搞清两个概念：1. 横向遍历时的重复；2. 纵向遍历时的重复。

显然，纵向遍历时允许重复，但横向遍历时要去重。

回溯三部曲：

• 递归函数参数：
  void backTracking(int[] candidates, int target, int startIndex)
• 递归终止条件：
  if(sum == target){

    res.add(new ArrayList<>(path));

    return;

  }
• 单层搜索逻辑：
  这里，我们要额外加一个判断同一树层（横向遍历）上的元素是否被使用过：
  if(i > startIndex && candidates[i] == candidates[i - 1])  continue;

  其余和正常回溯+剪枝过程没差别。

注意一下：该题的去重是先排序的。先排序后去重。

答案：

11.22：回溯算法-分割回文串（切割问题，较难，多细品）

题目：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]

分析：

这道题有几个难点：

• 需要意识到：分割问题的类似于组合问题
• 怎么将切割问题抽象为组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串

我们一个一个解决。先来看看组合问题和切割问题的共性：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。

显然，切割问题，也可以抽象为一棵树形结构：

接下来，怎么模拟切割线呢？首先这个问题显然是要用 startIndex 参数的，它既表示下一轮递归遍历的起始位置，也表示上一层已经确定了的分割线。而循环中的 i 则表示这一层试图寻找的新分割线。这里注意一下，从图中的表示来看，即使 i == startIndex，新分割线也要比旧分割线多一个跨度（i 表示的切割线位置是 startIndex + 1 表示的切割线位置，可以这么理解）。每一次递归都将 i + 1 传入给 startIndex，实际上就是移动旧分割线。

至于递归的终止条件，从树形结构的图中就可以看出，当上一层传入的旧切割线已经切到字符串最后面了，说明找到了一种切割方式，此时就是本层递归的终止条件。

截取子字符串的方法具体看代码。

答案：

11.26：回溯算法-复原IP地址

题目：

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201″ 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312″ 和 “192.168@1.1” 是 无效的 IP 地址。

分析：

显然，这题又是一个切割问题，只要是切割问题就可以使用回溯搜索法把所有可能性搜出来，只不过在上一题的基础上要对每一个切割部分做额外的条件判断。

但是，要注意，本题的终止条件和上一题不同，因为本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。用pointNum表示逗点数量，pointNum为3说明字符串分成了4段了，然后验证一下第四段是否合法，如果合法就加入到结果集里。

单层循环的逻辑里需要注意一下的是，当你把 ‘.’ 插入到字符串里时，后面的字符串长度实际上是加1了的，所以下层递归的起始切割位置不是传入 i + 1 而是 i + 2 。

答案：

11.27：回溯算法-子集问题

题目：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集。

示例：输入：nums = [1,2,3]，输出：[ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

分析：

乍一看会觉得这个问题和组合问题或切割问题很像，但其实两者有一个本质的区别：组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

所以显然，我们要在每一轮的递归遍历中，将每一个path都放入结果集中。

回溯三部曲：

• 递归函数参数：依然要用到 startIndex 来防止重复去元素。
• 递归终止条件：终止条件就是剩余集合为空，那么什么时候剩余集合为空呢？就是startIndex大于等于数组长度的时候，此时表示传入的选取索引（startIndex）已经超出数组了。所以其实这题都不需要终止条件，或者说终止条件就是for循环里的 startIndex > nums.size()。
• 单层搜索逻辑：逻辑就是最基础的回溯算法模版，但是注意求取子集问题，不需要任何剪枝，因为子集就是要遍历整棵树。

答案：

11.29：回溯算法-子集II

题目：

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

• 输入: [1,2,2]
• 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

分析：

这题相较于上一题就是多了一个去重的约束，实际做法就是 11.21：回溯算法-组合总和II的去重方法 + 上一题的子集问题的解法。详细思路看代码即可。

答案：

11.30：回溯算法-递增子序列

题目：

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例（这示例简直有病……）:

• 输入: [4, 6, 7, 7]
• 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

分析：

这题的重点之一是理解题面定义的递增子序列到底是什么。注意，这题的示例非常具有迷惑性！这题所谓的子序列是按照输入序列的顺序得到的，也就是说，不能改变输入序列的顺序，比如前两题的排序去重。不理解的话可以拿[7,4,7,5]这样的输入序列输出一下。接下来，为了方便讲解，下面都用[4,7,6,7]这个输入序列来举例。

回溯三部曲：

1. 递归函数参数-显然，本题求子序列，纵向遍历时元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置。
   backTracking(int[] nums, int startIndex)
2. 终止条件-本题类似于求子集问题，也是要遍历并记录树形结构的每一个节点，所以可以不加终止条件。只要递增序列的大小大于1就可以加入结果集中。
   if(path.size() > 1){
  res.add(new ArrayList<>(path));
}
3. 单层搜索逻辑-如上图所示，只不过要加一个大小的判断，并额外用HashSet来做层内去重。

答案：

12.1：回溯算法-全排列I（排列问题）

题目：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

• 输入: [1,2,3]
• 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

分析：

典型的排列问题。首先，排列是有序的，不如元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次，所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组，标记已经选择的元素。

回溯三部曲比较简单，直接看代码即可。

答案：

12.2：回溯算法-全排列II（强烈建议手推[0,1,2,2]，深入理解used数组在排列问题中的作用）

题目：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例：

• 输入：nums = [1,1,2]
• 输出： [[1,1,2], [1,2,1], [2,1,1]]

分析：

显然，这题和上一道排列问题的唯一区别就是要去重，而排列问题的去重其实和组合问题与子集问题的去重逻辑是一样的，都是先排序后去重。

同时，我们可以总结一下：一般来说，组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

回溯三部曲和代码的实现和之前没有太大的区别，唯一需要注意的一个关键点是去重的部分：

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

这个判断条件中的前两个条件和之前的去重逻辑差不多，没什么好说的。主要是注意一下used[i - 1] == false)这个（相较于组合问题先排序后去重时多出来的）条件，它的作用是保证程序所判断的 nums[i] 和 nums[i – 1] 是在同一树层中的判断，防止出现 nums[i] 在 nums[i – 1] 的下一层，但代码只判断了两者相同从而将其排出结果集。具体可以用[0,1,2,2]手推一下。

答案：

12.3：回溯算法补充-去重的另一种逻辑

题目：

去重相关题目：子集II 、组合总和II、全排列II。

分析：

之前面对这些涉及去重的题目时，我们都是用的先排序后去重的去重逻辑，但其实说到去重，我们第一时间往往想到的是用 set 去重，所以今天补充一下 set 的去重方法。

利用 HashSet 实现去重，要保证每一层独占一个set，因为我们要做的是树层（横向遍历）去重，如果将一个 set 作为全局变量，即便在单层搜索中插入再拔出，层与层之间都会互相影响。

代码实现具体如下。

答案：

全排列II：

public void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        HashSet<Integer> hashSet = new HashSet<>();//层去重
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i]))
                continue;
            if (used[i] == true)//枝去重
                continue;
            hashSet.add(nums[i]);//记录元素
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

子集II：

public void backtracking(int[] nums,int startIndex){
        reslut.add(new ArrayList<>(path));
        if(startIndex >= nums.length)return;
        HashSet<Integer> hashSet = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++){
            if(hashSet.contains(nums[i])){
                continue;
            }
            hashSet.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }

组合总和II：

public void backtracking(int[] candidates,int target,int sum,int startIndex){
        if( sum > target )return;
        if( sum == target ){
            result.add( new ArrayList<>(path) );
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for( int i = startIndex; i < candidates.length; i++){
            if( hashSet.contains(candidates[i]) ){
                continue;
            }
            hashSet.add(candidates[i]);
            path.add(candidates[i]);
            sum += candidates[i];
            backtracking(candidates,target,sum,i+1);
            path.removeLast();
            sum -= candidates[i];
        }
    }

12.4：回溯算法-重新安排行程（较难）

题目：

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

• 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
• 所有的机场都用三个大写字母表示（机场代码）。
• 假定所有机票至少存在一种合理的行程。
• 所有的机票必须都用一次 且 只能用一次。

示例 1：

• 输入：[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
• 输出：[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

示例 2：

• 输入：[[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
• 输出：[“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
• 解释：另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。但是它自然排序更大更靠后。

分析：

其实这题的最开始的难点在于你想不到用回溯算法来解决问题，就算想到了回溯算法，第一时间也不知道怎么用回溯算法的树形结构去分析这个问题。现在，我们来看看该题的回溯树形：

除此之外，还有几个难点：

1. 行程可能会出现死循环。
2. 怎么记录出发机场和目的机场的映射关系？
3. 怎么实现自然排序，从而返回最小的行程组合？
4. 该回溯的终止条件是什么？
5. 如何遍历一个机场对应的所有目的机场

我们来一一解决。死循环和自然排序的问题其实都和映射关系的设置有关。对于死循环，我们设置一个 Map<String, Map<String, Integer>> map 的映射关系，用Integer记录每个机场的可使用次数，只需在单层遍历时加个判断，就可以避免死循环的问题。对于自然排序以及最小行程组合，只需要用TreeMap实现后面的Map<String, Integer>即可，通过TreeMap用升序保存每个出发机场对应的目的机场，使得在树形结构的单条路径的遍历中总可以直接返回最短的行程组合，这也是为什么这次的backTracking函数的返回值为boolean。至于终止条件，找规律就可以发现，一旦行程里的机场数是航班数+1，就意味着找到了一种行程。最后，怎么遍历的问题看代码即可。

答案：

12.5：回溯算法-N皇后（棋盘问题）

题目：

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：

• 输入：n = 4
• 输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
• 解释：如上图所示，4 皇后问题存在两个不同的解法。

分析：

这个题主要的难点在于想不到用回溯算法，就算想到了，也不知道怎么将搜索过程抽象为一棵树。但是一旦想通了，就会变得很简单，最多在放置条件的编写上要花点功夫。

从图中，可以看出，棋盘的行就是这棵树的高度（递归的深度），棋盘的列就是树形结构中每一个节点的宽度（for循环的长度）。单层搜索逻辑得出。

只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。终止条件得出。

答案：

12.6：回溯算法-解数独（棋盘问题）（较难）

题目：

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。 空白格用 ‘.’ 表示。

示例：

提示：

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9×9 形式的。

分析：

解数独是典型且较难的棋盘问题。其本质上和N皇后的解法有相似之处，但是N皇后是一行只放一个皇后，也就是说这一行只要放了一个皇后就可以直接开始搜索下一行了，所以只需要一层for循环遍历列，递归来遍历行就行了。而本题则不行，棋盘的每一个位置都要放一个数字，所以解数独的树形结构要比N皇后更宽更深。一部分树形结构如下：（换行了遍历方式也是一样的）

回溯三部曲：

• 递归函数以及参数：因为解数独只要找到一个符合的条件就可以立刻返回，相当于只要遍历树中的唯一路径，所以需要使用boolean作为返回值。
  boolean backTracking(char[][] board, int startRow)
• 递归终止条件：本题不需要终止条件，只要找到一个正确解，即填满棋盘，所有层依次一起返回true即可。就算没有解，每一层递归在尝试完所有可能后，都会向上返回false。
• 单层搜索逻辑：一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一个for循环遍历所有可能的数字。尤其要留意一下放return的地方。至于判断棋盘是否合法，行和列上的判断是简单的，主要是9宫格的起始判断位置要多想一想，详细见代码。

答案：