题目:不同的二叉搜索树 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 种不同结构的二叉搜索树:
  12. 1 3 3 2 1
  13. \ / / / \ \
  14. 3 2 1 1 3 2
  15. / / \ \
  16. 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. public TreeNode clone(int val, TreeNode root) { // 重新创建一个新的子树
  42. if (root == null) return null; // 如果为null,返回
  43. TreeNode newTree = new TreeNode(val + root.val); // 创建节点时,不要忘了还要加上那个root。
  44. newTree.left = clone(val, root.left); // 递归左和右,和先序遍历很像。
  45. newTree.right = clone(val, root.right);
  46. return newTree; // 返回回去的这个节点正好跟在你需要的右子树上。
  47. }
  48. }