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

傷城~ 2023-03-01 05:54 11阅读 0赞

# 题目 #

[题目链接][Link 1]

### 题目描述 ###

给定一个整数 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));
      }
    }

[Link 1]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/