Given n, generate all structurally unique BST's (binary search trees) that store values 1...n

Solution: 根据[start, end]构造,取其中的i作为root,则[start, i - 1]为left, [i + 1, end]为right,产生的left和right的list两两组合

    public List<TreeNode> generateTrees(int n) {
        return generate(1, n);
    }
    private List<TreeNode> generate(int start, int end){
        List<TreeNode> result = new ArrayList<TreeNode>();
        if(start > end){
            result.add(null); //不能少
            return result;
        }
        if(start == end){
            result.add(new TreeNode(start));
            return result;
        }
        for(int i = start; i <= end; i++){
            List<TreeNode> left = generate(start, i - 1);
            List<TreeNode> right = generate(i + 1, end);
            for(TreeNode leftroot : left){
                for(TreeNode rightroot : right){
                    TreeNode root = new TreeNode(i);
                    root.left = leftroot;
                    root.right = rightroot;
                    result.add(root);
                }
            }
        }
        return result;
    }

.

results matching ""

    No results matching ""