LeetCode-T95-不同的二叉搜索树 II(unique-binary-search-trees-ii)

题目

题目链接

题目描述

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

样例

case1:

输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

1        3     3    2    1
  \      /      /     / \      \
  3    2    1    1  3     2
  /    /       \              \
2    1        2             3

题解

思路

二叉搜索树既二叉树的中序遍历，特点是：每个节点的左子树的所有节点的值都小于该节点，所有右子树的节点的值都大于该节点
因此我们给定根节点的值为x，则左子树的节点的值的范围为[1,x-1]，右子树的节点的值为[x+1,n]
而对于每一颗子树我们都可以以此内推，因此我们可以通过递归来解决这个问题
定义dfs(l,r) 返回(l,r)的子树集合 初始范围为(1,n)
边界条件为 l > r：返回空集合
          l == r: 返回单个节点集合，该节点左右子树为null
for(i,l,r) 以i为父节点递归获取左右子树集合 再组合以i为父节点的所有子树的集合 最后返回(l,r)的子树集合

代码

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
 * 思路：
 *     二叉搜索树既二叉树的中序遍历，特点是：每个节点的左子树的所有节点的值都小于该节点，所有右子树的节点的值都大于该节点
 *     因此我们给定根节点的值为x，则左子树的节点的值的范围为[1,x-1]，右子树的节点的值为[x+1,n]
 *     而对于每一颗子树我们都可以以此内推，因此我们可以通过递归来解决这个问题
 *     定义dfs(l,r) 返回(l,r)的子树集合  初始范围为(1,n)
 *     边界条件为 l > r：返回空集合
 *              l == r: 返回单个节点集合，该节点左右子树为null
 *     for(i,l,r) 以i为父节点递归获取左右子树集合 再组合以i为父节点的所有子树的集合 最后返回(l,r)的子树集合
 *
 * @author yingxiang
 */
public class LeetCode_95 {

  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;
    }
  }

  public List<TreeNode> generateTrees(int n) {
    return getAllSubTree(1,n);
  }

  public List<TreeNode> getAllSubTree(int l, int r) {
    List<TreeNode> trees = new ArrayList();
    if(l > r) {
      return trees;
    }

    if(l == r) {
      TreeNode node = new TreeNode(l, null, null);
      trees.add(node);
      return trees;
    }

    for(int i = l; i <= r; i++) {
      List<TreeNode> left = getAllSubTree(l,i-1);
      List<TreeNode> right = getAllSubTree(i+1,r);
      for(int j = 0; j < left.size(); j++) {
        for(int k = 0; k < right.size(); k++) {
          TreeNode node = new TreeNode(i, left.get(j), right.get(k));
          trees.add(node);
        }
        if(right.size() == 0) {
          TreeNode node = new TreeNode(i, left.get(j), null);
          trees.add(node);
        }
      }
      if(left.size() == 0) {
        for(int k = 0; k < right.size(); k++) {
          TreeNode node = new TreeNode(i, null, right.get(k));
          trees.add(node);
        }
      }
    }
    return trees;
  }

  public static void main(String[] args) {
    int n = 4;
    System.out.println(new LeetCode_95().generateTrees(n));
  }
}