leetcode 95. Unique Binary Search Trees II 唯一二叉搜索树

题意

Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]

解

上一题 96. Unique Binary Search Trees dfs即可，直接看代码

// Runtime: 1 ms, faster than 96.03% of Java online submissions for Unique Binary Search Trees II. //Memory Usage: 39.7 MB, less than 13.06% of Java online submissions for Unique Binary Search Trees II. public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateTrees(1, n); } private List<TreeNode> generateTrees(int m, int n) { if (m > n) return null; List<TreeNode> list = new ArrayList<>(); List<TreeNode> tmp = new ArrayList<>(); tmp.add(null); for (int i = m; i <= n; i++) { List<TreeNode> leftNodes = generateTrees(m, i - 1); List<TreeNode> rightNodes = generateTrees(i + 1, n); for (TreeNode leftNode : leftNodes == null ? tmp : leftNodes) { for (TreeNode rightNode : rightNodes == null ? tmp : rightNodes) { list.add(new TreeNode(i, leftNode, rightNode)); } } } return list; }