95.不同的二叉搜索树II

1、题目描述

2、解题思路

使用分治算法分析如下

1. 对于给定的数字n我们可以选择[1,n]之间的数字作为根节点一旦选择了数字i(1<=i<=n)根节点的左子树的候选序列就是[1,i-1]右子树的候选序列是[i+1,n]。很显然一旦确定根节点选择的值之后构造左子树和右子树和原问题相同也就是原问题可以分解为两个规模更小的子问题符合分治算法分的条件。
2. 现在需要考虑是否可以根据两个子问题获得原问题的解也就是如果我们知道了根节点为i时所有左子树的构造可能以及所有右子树的构造可能是否能够知道以i为根节点的所有二叉搜索树的构造可能
3. 答案是肯定的左子树和右子树的笛卡尔积再拼接上根节点就是原问题的解符合分治算法治的原则

3、解题代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<TreeNode> generateTrees(int n) {
    return solve(1, n);
  }

  public List<TreeNode> solve(int left, int right) {
    // 如果没有候选值可以选那么只能构造空
    if (left > right) {
      return null;
    }

    // 接收结果
    List<TreeNode> res = new ArrayList<>();
    if (left == right) {
      // 如果只有一个数字可以选那么只能构造拥有一个节点的树
      res.add(new TreeNode(left));
      return res;
    }

    // 第一层循环依次枚举根节点的值
    for (int i = left; i <= right; i++) {
      // 选择i作为根节点构造二叉搜索树那么左子树的候选值只能是
      // [left, i - 1]都比i小
      // 右子树的候选值只能是[i+1, right]都比i大
      // 递归求解[left, i-1]之间可以构造出多少二叉搜索树
      List<TreeNode> leftSet = solve(left, i - 1);
      // 递归求解[i+1, right]之间可以构造出多少二叉搜索树
      List<TreeNode> rightSet = solve(i + 1, right);
      // leftSet和rightSet不可能全为空
      // 走到这个for循环说明left和right之间至少有两个值其中一个
      // 给了根节点剩下的要么左子树右子树都有要么全在左子树要么
      // 全在右子树
      if (leftSet == null) {
        // 那就是只有右孩子
        for (TreeNode rightChild : rightSet) {
          TreeNode root = new TreeNode(i);
          root.right = rightChild;
          res.add(root);
        }
      } else if (rightSet == null) {
        // 那就是只有左孩子
        for (TreeNode leftChild : leftSet) {
          TreeNode root = new TreeNode(i);
          root.left = leftChild;
          res.add(root);
        }
      } else {
        // 左右孩子都有那么做左孩子集合和右孩子集合的笛卡尔积
        for (TreeNode leftChild : leftSet) {
          for (TreeNode rightChild : rightSet) {
            TreeNode root = new TreeNode(i);
            root.left = leftChild;
            root.right = rightChild;
            res.add(root);
          }
        }
      }
    }
    // 返回结果
    return res;
  }
}

4、提交结果