第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

二．解题思路

本题思路：采用递归+深度搜索的方式进行构建二叉搜索树。

步骤一：运用for循环依次将1-n当成根节点i进行搜索。

步骤二：当构建左子树时，递归函数（frist 到i-1）,构建右子树时，递归函数（i+1到end）。

步骤三：当在递归函数的最底部时，需要将每一层节点子树的可能性添加到list列表中，并返回给上一层。

步骤四：最终遍历结束，返回最终list表。

三．执行结果

执行用时 :2 ms, 在所有 java 提交中击败了99.49%的用户

内存消耗 :37.1 MB, 在所有 java 提交中击败了90.28%的用户

四． Java代码

class Solution {

    public List<TreeNode> generateTrees(int n) {

        if(n==0)

        {

            List<TreeNode> result=new ArrayList<TreeNode>();

            return result;

        }

        List<TreeNode> result=new ArrayList<TreeNode>();

        result=Tree(1,n);

        return result;

    }

     public List<TreeNode> Tree(int first,int end) {

        List<TreeNode> list=new ArrayList<TreeNode>();

        if(first>end) list.add(null);

        for(int i=first;i<=end;i++)

        {

        List<TreeNode> left=Tree(first,i-1);

        List<TreeNode> right=Tree(i+1, end);

        for(int m=0;m<left.size();m++ )

        {

            for(int n=0;n<right.size();n++)

            {

                TreeNode newroot=new TreeNode(i);

                newroot.left=left.get(m);

                newroot.right=right.get(n);

                list.add(newroot);

            }

        }

        }

        return list;

    }

}

巴特西

第95题：不同的二叉搜素树II

最新文章

热门文章