本文已参与「新人创造礼」活动,一起开启创造之路。

leetcode第95题

题目描绘（中等难度）

给一个 n，用1…n 这些数字生成一切或许的二分查找树。所谓二分查找树，定义如下：

1. 若恣意节点的左子树不空，则左子树上一切节点的值均小于它的根节点的值；
2. 若恣意节点的右子树不空，则右子树上一切节点的值均大于它的根节点的值；
3. 恣意节点的左、右子树也分别为二叉查找树；
4. 没有键值持平的节点。

解法一 回溯法

这是自己最早想到的一个思路。惯例的回溯思维，便是一般的一个 for 循环，测验刺进 1, 2 … n，然后进入递归，在本来的基础上持续测验刺进 1, 2… n。直到树包含了一切的数字。便是差不多下边这样的结构。

递归{
  递归出口；
  for(int i = 1;i<=n;i++){
    add(i);
    进入递归；
      remove(i);
   }
}
Copy

看一下详细的代码。

public List<TreeNode> generateTrees(int n) {
  List<TreeNode> ans = new ArrayList<TreeNode>();
  if (n == 0) {
    return ans;
   }
  TreeNode root = new TreeNode(0); //作为一个岗兵节点
  getAns(n, ans, root, 0);
  return ans;
}
​
private void getAns(int n, List<TreeNode> ans, TreeNode root, int count) {
  if (count == n) {
    //仿制当时树而且加到成果中
    TreeNode newRoot = treeCopy(root);
    ans.add(newRoot.right);
    return;
   }
  TreeNode root_copy = root;
  //测验刺进每个数
  for (int i = 1; i <= n; i++) {
    root = root_copy;
    //寻找要刺进的方位
    while (root != null) {
      //在左子树中刺进
      if (i < root.val) {
        //到了最左边
        if (root.left==null) {
          //刺进当时数字
          root.left = new TreeNode(i);
          //进入递归
          getAns(n, ans, root_copy, count + 1);
          //还原为 null，测验刺进下个数字
          root.left = null;
          break;
         }
        root = root.left;
      //在右子树中刺进
       } else if (i > root.val){
         //到了最右边
        if (root.right == null){
          //刺进当时数字
          root.right = new TreeNode(i);
          //进入递归
          getAns(n, ans, root_copy, count + 1);
          //还原为 null，测验刺进下个数字
          root.right = null;
          break;
         }
        root = root.right;
       //假如找到了持平的数字，就完毕，测验下一个数字
       } else {
        break;
       }
     }
   }
}
Copy

可是，理想很美丽，现实很骨感，出错了，便是回溯常常遇到的问题，呈现了重复解。

//第一种状况
​
第一次循环添加 2
  2
​
第2次循环添加 1
  2
 /
 1
​
第三次循环添加 3
  2
 / \ 
 1  3
​
//第二种状况
​
第一次循环添加 2
  2
​
第2次循环添加 3
  2
   \
   3
​
第三次循环添加 1
  2
 / \ 
 1  3
Copy

是的，因为每次循环都测验了一切数字，所以造成了重复。所以接下来便是解决防止重复数字的发生，可是通过种种尽力，都失败了，所以这种思路就此完毕，假如大家想出了防止重复的办法，欢迎和我交流。

解法二 递归

解法一彻底没有用到查找二叉树的性质，暴力测验了一切或许从而造成了重复。咱们能够使用一下查找二叉树的性质。左子树的一切值小于根节点，右子树的一切值大于根节点。

所以假如求 1…n 的一切或许。

咱们只需求把 1 作为根节点，[ ] 空作为左子树，[ 2 … n ] 的一切或许作为右子树。

2 作为根节点，[ 1 ] 作为左子树，[ 3…n ] 的一切或许作为右子树。

3 作为根节点，[ 1 2 ] 的一切或许作为左子树，[ 4 … n ] 的一切或许作为右子树，然后左子树和右子树两两组合。

4 作为根节点，[ 1 2 3 ] 的一切或许作为左子树，[ 5 … n ] 的一切或许作为右子树，然后左子树和右子树两两组合。

…

n 作为根节点，[ 1… n ] 的一切或许作为左子树，[ ] 作为右子树。

至于，[ 2 … n ] 的一切或许以及 [ 4 … n ] 以及其他状况的一切或许，能够使用上边的办法，把每个数字作为根节点，然后把一切或许的左子树和右子树组合起来即可。

假如只有一个数字，那么一切或许便是一种状况，把该数字作为一棵树。而假如是 [ ]，那就返回 null。

public List<TreeNode> generateTrees(int n) {
  List<TreeNode> ans = new ArrayList<TreeNode>();
  if (n == 0) {
    return ans;
   }
  return getAns(1, n);
​
}
​
private List<TreeNode> getAns(int start, int end) { 
  List<TreeNode> ans = new ArrayList<TreeNode>();
  //此时没有数字，将 null 加入成果中
  if (start > end) {
    ans.add(null);
    return ans;
   }
  //只有一个数字，当时数字作为一棵树加入成果中
  if (start == end) {
    TreeNode tree = new TreeNode(start);
    ans.add(tree);
    return ans;
   }
  //测验每个数字作为根节点
  for (int i = start; i <= end; i++) {
    //得到一切或许的左子树
    List<TreeNode> leftTrees = getAns(start, i - 1);
     //得到一切或许的右子树
    List<TreeNode> rightTrees = getAns(i + 1, end);
    //左子树右子树两两组合
    for (TreeNode leftTree : leftTrees) {
      for (TreeNode rightTree : rightTrees) {
        TreeNode root = new TreeNode(i);
        root.left = leftTree;
        root.right = rightTree;
        //加入到最终成果中
        ans.add(root);
       }
     }
   }
  return ans;
}
Copy

解法三 动态规划

大多数递归都能够用动态规划的思维重写，这道也不例外。从底部往上走，参考这儿。

举个例子，n = 3

数字个数是 0 的一切解
null
数字个数是 1 的一切解
1
2
3
数字个数是 2 的一切解，咱们只需求考虑连续数字
[ 1 2 ]
 1 
  \  
  2
  2
 /
 1
​
[ 2 3 ]
 2 
  \  
  3
  3
 /
 2
假如求 3 个数字的一切状况。
[ 1 2 3 ]
使用解法二递归的思路，便是分别把每个数字作为根节点，然后考虑左子树和右子树的或许
1 作为根节点，左子树是 [] 的一切或许，右子树是 [ 2 3 ] 的一切或许，使用之前求出的成果进行组合。
  1
 /  \
null  2
    \
     3
​
  1
 /  \
null  3
   /
   2 
​
2 作为根节点，左子树是 [ 1 ] 的一切或许，右子树是  [ 3 ] 的一切或许，使用之前求出的成果进行组合。
  2
 /  \
 1   3
​
3 作为根节点，左子树是 [ 1 2 ] 的一切或许，右子树是 [] 的一切或许，使用之前求出的成果进行组合。
   3
  /  \
 1  null
  \
  2
​
   3
  /  \
  2  null 
 /
 1
Copy

然后使用上边的思路基本上能够写代码了，便是求出长度为 1 的一切或许，长度为 2 的一切或许 … 直到 n。

可是咱们注意到，求长度为 2 的一切或许的时分，咱们需求求 [ 1 2 ] 的一切或许，[ 2 3 ] 的一切或许，这仅仅 n = 3 的状况。假如 n 等于 100，咱们需求求的更多了 [ 1 2 ] ， [ 2 3 ] ， [ 3 4 ] … [ 99 100 ] 太多了。能不能优化呢？

仔细观察，咱们能够发现长度是为 2 的一切或许其实只有两种结构。

  x 
 /  
y
​
y
 \
  x
Copy

看之前推导的 [ 1 2 ] 和 [ 2 3 ]，仅仅数字不相同，结构是彻底相同的。

[ 1 2 ]
  1 
  \  
   2
  2
  /
 1
​
[ 2 3 ]
  2 
  \  
   3
  3
  /
 2
Copy

所以咱们 n = 100 的时分，求长度是 2 的一切状况的时分，咱们没必要把 [ 1 2 ] ， [ 2 3 ] ， [ 3 4 ] … [ 99 100 ] 一切的状况都求出来，只需求求出 [ 1 2 ] 的一切状况即可。

推行到恣意长度 len，咱们其实只需求求 [ 1 2 … len ] 的一切状况就能够了。下一个问题随之而来，这些 [ 2 3 ] ， [ 3 4 ] … [ 99 100 ] 没求的怎么办呢？

举个例子。n = 100，此时咱们求把 98 作为根节点的一切状况，依据之前的推导，咱们需求长度是 97 的 [ 1 2 … 97 ] 的一切状况作为左子树，长度是 2 的 [ 99 100 ] 的一切状况作为右子树。

[ 1 2 … 97 ] 的一切状况刚好是 [ 1 2 … len ] ，已经求出来了。但 [ 99 100 ] 怎么办呢？咱们只求了 [ 1 2 ] 的一切状况。答案很明显了，在 [ 1 2 ] 的一切状况每个数字加一个误差 98，即加上根节点的值就能够了。

[ 1 2 ]
 1 
  \  
  2
  2
 /
 1
​
[ 99 100 ]
 1 + 98
  \  
  2 + 98
  2 + 98
 /
 1 + 98
​
即
 99 
  \  
  100
  100
 /
 99
Copy

所以咱们需求一个函数，实现树的仿制而且加上误差。

private TreeNode clone(TreeNode n, int offset) {
    if (n == null) {
        return null;
    }
    TreeNode node = new TreeNode(n.val + offset);
    node.left = clone(n.left, offset);
    node.right = clone(n.right, offset);
    return node;
}
Copy

通过上边的一切分析，代码能够写了，总体思维便是求长度为 2 的一切状况，求长度为 3 的一切状况直到 n。而求长度为 len 的一切状况，咱们只需求求出一个代表 [ 1 2 … len ] 的一切状况，其他的话加上一个误差，加上当时根节点即可。

public List<TreeNode> generateTrees(int n) {
  ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
  dp[0] = new ArrayList<TreeNode>();
  if (n == 0) {
    return dp[0];
   }
  dp[0].add(null);
  //长度为 1 到 n
  for (int len = 1; len <= n; len++) {
    dp[len] = new ArrayList<TreeNode>();
    //将不同的数字作为根节点，只需求考虑到 len
    for (int root = 1; root <= len; root++) {
      int left = root - 1; //左子树的长度
      int right = len - root; //右子树的长度
      for (TreeNode leftTree : dp[left]) {
        for (TreeNode rightTree : dp[right]) {
          TreeNode treeRoot = new TreeNode(root);
          treeRoot.left = leftTree;
          //克隆右子树而且加上误差
          treeRoot.right = clone(rightTree, root);
          dp[len].add(treeRoot);
         }
       }
     }
   }
  return dp[n];
}
​
private TreeNode clone(TreeNode n, int offset) {
  if (n == null) {
    return null;
   }
  TreeNode node = new TreeNode(n.val + offset);
  node.left = clone(n.left, offset);
  node.right = clone(n.right, offset);
  return node;
}
Copy

值得注意的是，一切的左子树咱们没有 clone ，也便是许多子树被共享了，在内存中就会是下边的样子。

也便是左子树用的都是之前的子树，没有开辟新的空间。

解法四 动态规划 2

解法三的动态规划彻底是模仿了解法二递归的思维，这儿再介绍另一种思维，会更好理解一些。参考这儿。

考虑 [] 的一切解
null
考虑 [ 1 ] 的一切解
1
考虑 [ 1 2 ] 的一切解
  2
 /
1
 1
  \
   2
考虑 [ 1 2 3 ] 的一切解
    3
   /
  2
 /
1
   2
  / \
 1   3
   3
  /
 1
  \
   2
   1
     \
      3
     /
    2
  1
    \
     2
      \
       3
Copy

仔细分析，能够发现一个规则。首先咱们每次新添加的数字大于之前的一切数字，所以新添加的数字呈现的方位只或许是根节点或者是根节点的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子等等，总归一定是右边。其次，新数字所在方位本来的子树，改为当时刺进数字的左孩子即可，因为刺进数字是最大的。

关于下边的解
  2
 /
1
然后添加 3
1.把 3 放到根节点
    3
   /
  2
 /
1

2. 把 3 放到根节点的右孩子
   2
  / \
 1   3
关于下边的解
 1
  \
   2
然后添加 3
1.把 3 放到根节点
    3
   /
  1
   \
    2

2. 把 3 放到根节点的右孩子，本来的子树作为 3 的左孩子       
      1
        \
         3
        /
      2

3. 把 3 放到根节点的右孩子的右孩子
  1
    \
     2
      \
       3
Copy

以上便是依据 [ 1 2 ] 推出 [ 1 2 3 ] 的一切过程，能够写代码了。因为求当时的一切解只需求上一次的解，一切咱们只需求两个 list，pre 保存上一次的一切解， cur 核算当时的一切解。

public List<TreeNode> generateTrees(int n) {
  List<TreeNode> pre = new ArrayList<TreeNode>();
  if (n == 0) {
    return pre;
   }
  pre.add(null);
  //每次添加一个数字
  for (int i = 1; i <= n; i++) {
    List<TreeNode> cur = new ArrayList<TreeNode>();
    //遍历之前的一切解
    for (TreeNode root : pre) {
      //刺进到根节点
      TreeNode insert = new TreeNode(i);
      insert.left = root;
      cur.add(insert);
      //刺进到右孩子，右孩子的右孩子...最多找 n 次孩子
      for (int j = 0; j <= n; j++) {
        TreeNode root_copy = treeCopy(root); //仿制当时的树
        TreeNode right = root_copy; //找到要刺进右孩子的方位
        int k = 0;
        //遍历 j 次找右孩子
        for (; k < j; k++) {
          if (right == null)
            break;
          right = right.right;
         }
        //到达 null 提前完毕
        if (right == null)
          break;
        //保存当时右孩子的方位的子树作为刺进节点的左孩子
        TreeNode rightTree = right.right;
        insert = new TreeNode(i);
        right.right = insert; //右孩子是刺进的节点
        insert.left = rightTree; //刺进节点的左孩子更新为刺进方位之前的子树
        //加入成果中
        cur.add(root_copy);
       }
     }
    pre = cur;
​
   }
  return pre;
}
​
​
private TreeNode treeCopy(TreeNode root) {
  if (root == null) {
    return root;
   }
  TreeNode newRoot = new TreeNode(root.val);
  newRoot.left = treeCopy(root.left);
  newRoot.right = treeCopy(root.right);
  return newRoot;
}
Copy

总结

解法二和解法四算作惯例的思路，比较简单想到。解法三，发现同构的操作真的是神仙操作了，服！