leetcode 95-96 Unique Binary Search Trees I-II

タイトルの要求

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

は、1−nというn−1個の数字で構成できる、すべての検索ツリーとその個数を返します。
考え方とコード
二叉の木の数を単純に計算すれば、これは完全に規則問題になります。私たちは1から規則を探すことができます。1：11、2：12、211、2、3：123、132、213、312、321
私たちはdpで記録できます。どのノードをrootノードとしても、左サブツリーの要素と右サブツリーの要素は固定されています。つまり、root値がiであると仮定すると、左サブツリーの要素は［1…i−1］であり、右サブツリーの要素は［i＋1…n］である。したがって、現在のrootノードで生成されることができる平衡二叉樹の数は、すなわち、左サブツリーの数＊右サブツリーの数である。ここで int[] n n 。

    public int numTrees(int n) {
        int[] nums = new int[n+1];
        for(int i = 0 ; i <= n ; i++){
            if(i==0 || i==1) nums[i] = 1;
            else{
                for(int j = 1 ; j<=i ; j++){
                    nums[i] += nums[j-1]*nums[i-j];
                }
            }
        }
        return nums[n];
    }

具体的な木の形態に戻るには、バックトラックの再帰的な形ですべてのバランスのとれた二叉の木を見つける必要があります。再帰の過程では、現在のノードをルートノードとするすべての平衡二叉ツリーを見つけ、結果をリスト形式で前の段階の呼び出しに戻します。

    public List generateTrees(int n) {
        if(n==0) return new ArrayList();
        return generateTrees(1,n);
    }
    public List generateTrees(int start, int end){
        List result = new ArrayList();
        if(start>end){
            result.add(null);
        }else if(start==end){
            result.add(new TreeNode(start));
        }else{
            for(int i = start ; i<=end ; i++){
                List left = generateTrees(start, i-1);
                List right = generateTrees(i+1, end);
                for(TreeNode tempLeft : left){
                    for(TreeNode tempRight : right){
                        TreeNode root = new TreeNode(i);
                        root.left = tempLeft;
                        root.right = tempRight;
                        result.add(root);
                    }
                }
            }
            
        }
        return result;
        
    }

もっと多くの開発技術を知りたいです。面接教程とインターネット会社の中で推します。不定期で福祉が支給されますよ。