题目：不同的二叉搜索树 II

  • 给定一个整数n，生成所有由1...n为节点所组成的二叉搜索树。
示例:
  1. 输入: 3
  2. 输出:
  3. [
  4.   [1,null,3,2],
  5.   [3,2,null,1],
  6.   [3,1,null,null,2],
  7.   [2,1,3],
  8.   [1,null,2,null,3]
  9. ]
  10. 解释:
  11. 以上的输出对应以下 5 种不同结构的二叉搜索树：
  13.    1         3     3      2      1
  14.     \       /     /      / \      \
  15.      3     2     1      1   3      2
  16.     /     /       \                 \
  17.    2     1         2                 3

来源：力扣（LeetCode）第95题

链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii

分析：

  • 可以使用递归，但我怕超时就没写。
  • 但是几乎所有的递归都可以转换为动态规划，所以这题用dp求解。
  • 思路和前面找个数一样，状态都是第n个数的内容，选择是谁为根节点。
  • 不一样的是状态转移方程稍稍有点复杂，我在代码中说明。

代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public List<TreeNode> generateTrees(int n) {
  12.         List<TreeNode>[] dp = new ArrayList[n+1];
  13.         dp[0] = new ArrayList(); // 如果left或right为0，就会出现空指针异常。
  14.         if (n == 0) return dp[0];
  15.         dp[0].add(null);// 如果不加null，那么后面当left或right为0时，就不会执行for循环。而一旦left不执行，right也会被跳过。
  16.         for (int i = 1; i <= n; i++) {
  17.             dp[i] = new ArrayList();
  18.             for (int root = 1; root <= i; root++) {
  19.                 int left = root - 1; // root为根节点，left是root左边的节点数。
  20.                 int right = i - root;// 同理，right为root右边的节点数。
  21.                 /*
  22.                     假设n为5，root是3，那么左边有2个节点，所以去dp[2]里面找，右边也有两个节点4,5。所以还去dp[2]里面找。
  23.                     因为只有dp[2]里面都是2个节点的数。但是dp[2]中的数只有1和2，我们要的是4,5。
  24.                     我们不妨将1,2加上root，你会发现正好是4,5。
  25.                     所以得到结论，左子树的值直接找前面节点数一样的dp索引，右子树的值也找前面一样的dp索引,
  26.                     但是你需要加上root才能保证val是你需要的，所以右子树要重新创建，不然会破坏前面的树。
  27.                 */
  28.                 // 如果dp[left]里有两种可能，dp[right]里有三种可能，那么总共有6种可能。
  29.                 for (TreeNode leftTree : dp[left]) {
  30.                     for (TreeNode rightTree : dp[right]) {
  31.                         TreeNode newRoot = new TreeNode(root); // 这个是每一种可能的root节点。
  32.                         newRoot.left = leftTree; // 左子树直接连接。
  33.                         newRoot.right = clone(root, rightTree); // 右子树创建一个新的树。
  34.                         dp[i].add(newRoot); // 将一种可能加入dp中。
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.         return dp[n]; // 这个不用多说，答案在第n个数上。
  40.     }
  41.     
  42.     public TreeNode clone(int val, TreeNode root) { // 重新创建一个新的子树
  43.         if (root == null) return null; // 如果为null，返回
  44.         TreeNode newTree = new TreeNode(val + root.val); // 创建节点时，不要忘了还要加上那个root。
  45.         newTree.left = clone(val, root.left); // 递归左和右，和先序遍历很像。
  46.         newTree.right = clone(val, root.right);
  47.         return newTree; // 返回回去的这个节点正好跟在你需要的右子树上。
  48.     }
  49. }