什么是决策树

​ 在学习回溯算法前我们需要去了解一下什么是决策树，官方解释太繁琐，大概翻译成这样：

• 决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
• 

回溯算法框架

​ 了解了决策树之后，会发现所谓回溯算法的问题其实就是决策树的遍历问题。

​ 我们需要考虑三个问题

• 路径：当前已经做出的选择（走过的,总体相当于全排列）
• 选择列表：当前可以往下走的选择（未走过，可以走的）
• 结束条件：到决策树的底层后无法再做出选择
• 

​ 看看框架长啥样

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        #做选择
        将该选择从选择列表移除
    	路径.add(选择)
        backtrack(路径, 选择列表)
        撤销选择
        #路径.remove(选择)
    	将该选择再加入选择列表

实战一下，解决 N 皇后问题

​ 题目描述：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击，皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。根据输入的行数返回所有可行的放置方法。

​ 问题本质： 其实就是跟全排列差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

​ 解题思路：

• 建一个 res 数组用于返回，建一个临时数组 temp 存放某种可行放置方法
• 初始化 temp,每个元素以’.’填充
• 套用框架，建立回溯函数 backtrack
• backtrack 函数信息
  • 默认小于当前行 row 的其他行已经成功放置了皇后
  • 选择列表为当前行的所有列
  • 结束条件是当前行超过题目输入的行数，满足结束条件说明该放置方法可行，将其加入 res 结果数组，这里会遇到深拷贝，浅拷贝的问题
  • 在根据选择列表做选择前需要判定该项是否合法
• 建立判定合法函数 isValid 进行判定
  • 先判断当前列有没有放置皇后互相冲突
  • 然后分别检查右上方和左上方

​ 代码

var solveNQueens = function (n) {
    let res = []
    let temp = []
    for (let i = 0; i < n; i++) {
        temp.push(Array(n).fill('.'))
    }
    traceBack(res,temp, 0)
    return res
};
function traceBack(res,temp, row) {
    let n = temp[0].length
    if (row == n) {
        let item=[]
        for(let i=0;i<n;i++){
            let t=[]
            for(let j=0;j<n;j++){
                t.push(temp[i][j])
            }
            item.push(t.join(""))
        }
        res.push(item)
        return
    }
    for (let col = 0; col < n; col++) {
        if (!isValid(temp, row, col)) {
            continue
        }
        temp[row][col] = 'Q'
        traceBack(res,temp, row + 1)
        temp[row][col] = '.'
    }

}
function isValid(temp, row, col) {
    let n = temp[0].length
    for (let i = 0; i < n; i++) {
        if (temp[i][col] == 'Q') {
            return false
        }
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (temp[i][j] == 'Q') {
            return false
        }
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (temp[i][j] == 'Q') {
            return false
        }
    }
    return true
}

深拷贝浅拷贝的疑惑

• 在往 res 添加可行解数组时，如果直接添加 temp 变量，后续 temp 改变会导致之前添加过的全部同步更新为 temp 当前值，因为 temp 变量只是数组实际存储在堆空间的地址引用值而已。

• 但疑惑的是，我通过新建一个临时变量 item 去利用一些深拷贝的方法将 temp 数组拷贝到 item，res 再添加 item，都失效了，还是会同步更新

  
  let item=temp.slice(0)
  let item=temp.concat()
  let [...item]=temp
  // 以上三种方法都失效了，所以用了最笨的 for 循环挨个赋值