LeetCode/95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II

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

示例 ：

输入：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

提示：

• 0 <= n <= 8

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

这道题目前没有想出太好的思路，就是参考官方题解。首先要明确二叉搜索树的结构，二叉搜索树就是每一个结点的左子树都小于该根结点的值，右子树都大于每个根结点的值。我们可以将输入的n分为两个集合，以每次遍历到的i结点为根结点，递归构建1~i-1的左子树，递归构建i+1~n的右子树。最后我们要遍历所有的结果，一共会有 leftTreeNodes.size()*rightTreeNodes.size()种情况，我们固定左子树，遍历右子树，将所有的可能情况都遍历完全。

具体代码如下：

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        //如果给定数为0，则返回空，否则进行递归调用
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return buildTrees(1, n);
    }

    public List<TreeNode> buildTrees(int begin, int end) {
        //用于存放所有树结果
        List<TreeNode> resultNode = new LinkedList<TreeNode>();

        //如果begin > end，当前二叉树为空，即为跳出条件
        if (begin > end) {
            resultNode.add(null);
            return resultNode;
        }

        for (int i = begin; i < end; i++) {
            //递归生成左子树和右子树
            List<TreeNode> leftTreeNodes = buildTrees(begin, i - 1);
            List<TreeNode> rightTreeNodes = buildTrees(i + 1, end);

            //一共会有leftTreeNodes.size()*rightTreeNodes.size()种情况
            //固定左子树，然后和不同的右子树搭配，将所有的情况加入resultNode中返回
            for (TreeNode leftTreeNode : leftTreeNodes) {
                for (TreeNode rightTreeNode : rightTreeNodes) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftTreeNode;
                    treeNode.right = rightTreeNode;
                    resultNode.add(treeNode);
                }
            }
        }
        return resultNode;
    }
}


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