题目

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

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

解

class Solution {public List<TreeNode> generateTrees(int n) {return dfs(1, n);}public List<TreeNode> dfs(int left, int right) {List<TreeNode> result = new ArrayList<>();if (left > right) {result.add(null);return result;}if (left == right) {result.add(new TreeNode(left));return result;}for (int i = left; i <= right; i++) {List<TreeNode> leftList = dfs(left, i - 1);List<TreeNode> rightList = dfs(i + 1, right);for (TreeNode leftNode : leftList) {for (TreeNode rightNode : rightList) {TreeNode root = new TreeNode(i);root.left = leftNode;root.right = rightNode;result.add(root);}}}return result;}
}