题目大意

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
image.png

解题思路

  • 递归方式
  • 为每一个[min,max] 区间的跟节点创建一个root

    具体的执行流程如下

终止条件 min> max 时 直接 返回rst
for 循环对每一个跟节点构建一个bst tree [min,max]
左子树 ，右子树 递归
1.如果 左右子树 都为0 时 直接返回单节点的一个bst
2.如果左子树为0右子树不为0时，为当前的每一个右子树构建一个root，他的指针指向当前的右子树
3.如果右子树为0，左子树不为0时，为当前的每一个左子树构建一个root，他的指针指向 当前的左子树
4.如果都不为0 时，以当前节点构建一个root，遍历左右子树，指向有效的左右子树
5.返回rst

  1. //给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
  2. //
  3. // 
  4. //
  5. // 
  6. // 
  7. // 示例 1： 
  8. //
  9. // 
  10. //输入：n = 3
  11. //输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
  12. // 
  13. //
  14. // 示例 2： 
  15. //
  16. // 
  17. //输入：n = 1
  18. //输出：[[1]]
  19. // 
  20. //
  21. // 
  22. //
  23. // 提示： 
  24. //
  25. // 
  26. // 1 <= n <= 8 
  27. // 
  28. // 
  29. // 
  30. // Related Topics 树 二叉搜索树 动态规划 回溯 二叉树 
  31. // 👍 965 👎 0
  34. package leetcode.editor.cn;
  36. import com.qjx.leetcode.common.TreeNode;
  38. import java.util.ArrayList;
  39. import java.util.List;
  41. class UniqueBinarySearchTreesIi {
  42.     public static void main(String[] args) {
  43.         Solution solution = new UniqueBinarySearchTreesIi().new Solution();
  44.         System.out.println(solution.generateTrees(3));
  45.     }
  46.     //leetcode submit region begin(Prohibit modification and deletion)
  48.     /**
  49.      * Definition for a binary tree node.
  50.      * public class TreeNode {
  51.      * int val;
  52.      * TreeNode left;
  53.      * TreeNode right;
  54.      * TreeNode() {}
  55.      * TreeNode(int val) { this.val = val; }
  56.      * TreeNode(int val, TreeNode left, TreeNode right) {
  57.      * this.val = val;
  58.      * this.left = left;
  59.      * this.right = right;
  60.      * }
  61.      * }
  62.      */
  63.     class Solution {
  64.         public List<TreeNode> generateTrees(int n) {
  65.             return helper(1, n);
  66.         }
  68.         /**
  69.          * 终止条件  min>  max  时 直接 返回rst
  70.          * for 循环对每一个跟节点构建一个bst tree [min,max]
  71.          * 左子树 ，右子树 递归
  72.          * 1.如果 左右子树 都为0 时  直接返回单节点的一个bst
  73.          * 2.如果左子树为0右子树不为0时，为当前的每一个右子树构建一个root，他的指针指向当前的右子树
  74.          * 3.如果右子树为0，左子树不为0时，为当前的每一个左子树构建一个root，他的指针指向 当前的左子树
  75.          * 4.如果都不为0 时，以当前节点构建一个root，遍历左右子树，指向有效的左右子树
  76.          * 5.返回rst
  77.          *
  78.          * @param min
  79.          * @param max
  80.          * @return
  81.          */
  82.         private List<TreeNode> helper(int min, int max) {
  83.             List<TreeNode> resut = new ArrayList<>();
  84.             //终止条件  min>  max  时 直接 返回rst
  85.             if (min > max) {
  86.                 return resut;
  87.             }
  88.             //for 循环对每一个跟节点构建一个bst tree [min,max]
  89.             for (int rt = min; rt <= max; rt++) {
  90.                 List<TreeNode> left = helper(min, rt - 1);
  91.                 List<TreeNode> right = helper(rt + 1, max);
  92.                 if (right.size() == 0 && left.size() == 0) {
  93.                     TreeNode root = new TreeNode(rt);
  94.                     resut.add(root);
  95.                 } else if (left.size() == 0) {
  96.                     for (TreeNode r : right) {
  97.                         TreeNode root = new TreeNode(rt);
  98.                         root.right = r;
  99.                         resut.add(root);
  100.                     }
  101.                 } else if (right.size() == 0) {
  102.                     for (TreeNode l : left) {
  103.                         TreeNode root = new TreeNode(rt);
  104.                         root.left = l;
  105.                         resut.add(root);
  106.                     }
  107.                 } else {
  108.                     //左右子树都不为0时
  109.                     for (TreeNode l : left) {
  110.                         for (TreeNode r : right) {
  111.                             TreeNode root = new TreeNode(rt);
  112.                             root.left = l;
  113.                             root.right = r;
  114.                             resut.add(root);
  115.                         }
  116.                     }
  117.                 }
  118.             }
  119.             return resut;
  120.         }
  121.     }
  122. //leetcode submit region end(Prohibit modification and deletion)
  124. }