LeetCode095——不同的二叉搜索树 II

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/

题目描述：

知识点：树、递归

思路：根据二叉搜索树的定义递归实现

和LeetCode096——不同的二叉搜索树相比，本题需要求出不同的二叉搜索树的具体实现，难度更大一些，但其实本质上是一样的。只需在递归函数中传递一个ArrayList集合保存构成二叉搜索树的数字即可。

递归终止条件：

如果传递进递归函数的arrayList中只有一个元素，显然，该二叉树列表中只有一颗树，这棵树只有一个根结点，其值为arrayList中唯一元素的值。

递归过程：

遍历arrayList中的所有值，将其分成小于当前节点的一部分less和大于当前节点的一部分greater。

（1）如果less和greater均至少含有一个元素，则我们分别递归调用得到其左子树列表和右子树列表。

（2）如果less和greater中有一个没有元素，则我们将相应的左子树或右子树置为null。

需要注意的是：

tempNode，即递归过程中根结点的定义需要在遍历左子树列表leftTreeNodeList和右子树列表rightTreeNodeList时定义。

时间复杂度和空间复杂度均是O(n ^ n)。

JAVA代码：

public class Solution {

    public List<TreeNode> generateTrees(int n) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            arrayList.add(i);
        }
        List<TreeNode> list = generateTrees(arrayList);
        return list;
    }

    private List<TreeNode> generateTrees(ArrayList<Integer> arrayList) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        if (arrayList.size() == 1) {
            TreeNode treeNode = new TreeNode(arrayList.get(0));
            treeNodeList.add(treeNode);
            return treeNodeList;
        }
        for (int i = 0; i < arrayList.size(); i++) {
            ArrayList<Integer> less = new ArrayList<>();
            ArrayList<Integer> greater = new ArrayList<>();
            for (int j = 0; j < arrayList.size(); j++) {
                if (i == j) {
                    continue;
                }
                if (arrayList.get(j) < arrayList.get(i)) {
                    less.add(arrayList.get(j));
                } else {
                    greater.add(arrayList.get(j));
                }
            }
            if (less.size() != 0 && greater.size() != 0) {
                List<TreeNode> leftTreeNodeList = generateTrees(less);
                List<TreeNode> rightTreeNodeList = generateTrees(greater);
                for (TreeNode leftTreeNode : leftTreeNodeList) {
                    for (TreeNode rightTreeNode : rightTreeNodeList) {
                        TreeNode tempNode = new TreeNode(arrayList.get(i));
                        tempNode.left = leftTreeNode;
                        tempNode.right = rightTreeNode;
                        treeNodeList.add(tempNode);
                    }
                }
            }else if(less.size() == 0 && greater.size() != 0){
                List<TreeNode> rightTreeNodeList = generateTrees(greater);
                for (TreeNode rightTreeNode : rightTreeNodeList) {
                    TreeNode tempNode = new TreeNode(arrayList.get(i));
                    tempNode.left = null;
                    tempNode.right = rightTreeNode;
                    treeNodeList.add(tempNode);
                }
            }else if(less.size() != 0 && greater.size() == 0){
                List<TreeNode> leftTreeNodeList = generateTrees(less);
                for (TreeNode leftTreeNode : leftTreeNodeList) {
                    TreeNode tempNode = new TreeNode(arrayList.get(i));
                    tempNode.left = leftTreeNode;
                    tempNode.right = null;
                    treeNodeList.add(tempNode);
                }
            }
        }
        return treeNodeList;
    }
}

LeetCode解题报告：