n個の結点、異なる形態の二叉樹(数+生成)
11562 ワード
テーマリンク:
異なる二叉で木を検索:http://www.lintcode.com/zh-cn/problem/unique-binary-search-trees/
異なる二叉ルックアップツリーII:http://www.lintcode.com/zh-cn/problem/unique-binary-search-trees-ii/
異なる形態の二叉木の数:
サンプル
n=3を与えると、5つの異なる形態の二叉ルックアップツリーがあります。
n=1の場合、1つのルートノードだけがある場合、1つの形態の2つのツリーしか構成できず、nつのノードで構成できる2つのツリーの数はh(n)と表され、h(1)=1となると分析することができる。h(0)=0
n=2の場合、1つのルートノードが固定され、2-1つのノードがあります。このノードは、(1、0)、(0、1)の2つのグループに分けることができる。左に1つ置いて、右に0つ置いてください。または左に0個を置き、右に1つを置く。つまり、h(2)=h(0)**h(1)+h(1)*h(0)=2であれば、2つの形態の二叉樹を構成することができる。
n=3の場合、1つのルートノードが固定され、2つのノードがあります。この2つのノードは、(2,0)、(1,1)、(0,2)の3つのグループに分けることができる。つまりh(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5であれば、5種類の形態の二叉樹を構成することができる。
これを類推すると、n>=2の場合、構成可能な二叉樹の数はh(n)=h(0)*h(n-1)+h(1)*h(n-2)+h(n-1)*h(0)種であり、Catalan数の定義に符合し、直接に通項式を利用して結果を得る。
令h(1)=1、h(0)=1、catalan数(カルテル数)は再帰式を満足する:
h(n)=h(0)*h(n-1)+h(1)*h(n-2)+h(n-1)h(0)(n>=2)
別の再帰式:
h(n)=((4*n-2)/(n+1)*h(n-1);
デリバリー関係の解は次の通りです。
h(n)=C(2 n,n)/(n+1)(n=1,2,3,…)
この前に言った「N個の数は順次にスタックに入るが、出庫順はどれぐらいあるか?」 同じように使っているのもカトラン数です。
http://www.cnblogs.com/hujunzheng/p/4845354.html
コード
異なる形態のツリーを構築する:
サンプル
n=3を与え、5つの異なる形態のすべての二叉ルックアップツリーを生成する。
アルゴリズム
まず弱々しく自分の間違った実現を言います。再帰的に実現する時に異なる二叉樹を得るため、n個の結点がちょうど二叉樹を生成したとどう判断しますか?そこで一つの変数でuseNode(=0)を使って、現在はいくつの結点を使ってツリーを作っているかを表します。useNodeがnに等しい時に、要求に合った木ができたと説明しました。それから、先ほど作った木をコピーして、vectorに入れて、次の条件に合う二叉樹を作り続けます。
エラーコード:
正しいコード:
転載先:https://www.cnblogs.com/hujunzheng/p/5040334.html
異なる二叉で木を検索:http://www.lintcode.com/zh-cn/problem/unique-binary-search-trees/
異なる二叉ルックアップツリーII:http://www.lintcode.com/zh-cn/problem/unique-binary-search-trees-ii/
異なる形態の二叉木の数:
サンプル
n=3を与えると、5つの異なる形態の二叉ルックアップツリーがあります。
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析n=1の場合、1つのルートノードだけがある場合、1つの形態の2つのツリーしか構成できず、nつのノードで構成できる2つのツリーの数はh(n)と表され、h(1)=1となると分析することができる。h(0)=0
n=2の場合、1つのルートノードが固定され、2-1つのノードがあります。このノードは、(1、0)、(0、1)の2つのグループに分けることができる。左に1つ置いて、右に0つ置いてください。または左に0個を置き、右に1つを置く。つまり、h(2)=h(0)**h(1)+h(1)*h(0)=2であれば、2つの形態の二叉樹を構成することができる。
n=3の場合、1つのルートノードが固定され、2つのノードがあります。この2つのノードは、(2,0)、(1,1)、(0,2)の3つのグループに分けることができる。つまりh(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5であれば、5種類の形態の二叉樹を構成することができる。
これを類推すると、n>=2の場合、構成可能な二叉樹の数はh(n)=h(0)*h(n-1)+h(1)*h(n-2)+h(n-1)*h(0)種であり、Catalan数の定義に符合し、直接に通項式を利用して結果を得る。
令h(1)=1、h(0)=1、catalan数(カルテル数)は再帰式を満足する:
h(n)=h(0)*h(n-1)+h(1)*h(n-2)+h(n-1)h(0)(n>=2)
別の再帰式:
h(n)=((4*n-2)/(n+1)*h(n-1);
デリバリー関係の解は次の通りです。
h(n)=C(2 n,n)/(n+1)(n=1,2,3,…)
この前に言った「N個の数は順次にスタックに入るが、出庫順はどれぐらいあるか?」 同じように使っているのもカトラン数です。
http://www.cnblogs.com/hujunzheng/p/4845354.html
コード
class Solution {
public:
/**
* @paramn n: An integer
* @return: An integer
*/
long long C(int n, int m){
n = n-m+1;
long long ans = 1;
for(int i=1; i<=m; ++i){
ans *= n++;
ans /= i;
}
return ans;
}
int numTrees(int n) {
// write your code here
return C(2*n, n)/(n+1);
}
};
異なる形態のツリーを構築する:
サンプル
n=3を与え、5つの異なる形態のすべての二叉ルックアップツリーを生成する。
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
実際には、例によって、n個の結点構造の異なる形態の二叉樹の過程が、1,2,3....n個の結点を列挙し、それぞれの結点がルート結点(root、1<=root<=n)であると仮定すれば、(1,2.. root-1)と(root+1,root+2…n)はそれぞれrootの左右子樹である。上記のプロセスを繰り返していくごとに、最終的にはすべての形態の二叉樹が得られます。アルゴリズム
まず弱々しく自分の間違った実現を言います。再帰的に実現する時に異なる二叉樹を得るため、n個の結点がちょうど二叉樹を生成したとどう判断しますか?そこで一つの変数でuseNode(=0)を使って、現在はいくつの結点を使ってツリーを作っているかを表します。useNodeがnに等しい時に、要求に合った木ができたと説明しました。それから、先ほど作った木をコピーして、vectorに入れて、次の条件に合う二叉樹を作り続けます。
エラーコード:
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @paramn n: An integer
* @return: A list of root
*/
vector ans;
int cntNode=0;//
TreeNode *curRoot = NULL;
void copyT(TreeNode * &tmp, TreeNode *T){
if(T){
tmp = new TreeNode(T->val);
copyT(tmp->left, T->left);
copyT(tmp->right, T->right);
}
}
void buildT(TreeNode * &T, int ld, int rd, int useNode){
if(ld > rd) return;
for(int root=ld; root<=rd; ++root){
T = new TreeNode(root);
if(ld==1 && rd==cntNode)
curRoot = T;
if(useNode+1==cntNode){// ,
TreeNode *tmp = NULL;
copyT(tmp, curRoot);
ans.push_back(tmp);
}
buildT(T->left, ld, root-1, useNode+1);
buildT(T->right, root+1, rd, useNode+root-ld+1);
}
}
vector generateTrees(int n) {
// write your code here
cntNode = n;
TreeNode *T = NULL;
buildT(T, 1, n, 0);
if(n == 0) ans.push_back(T);
return ans;
}
};
その後、運転したら、間違った答えと正しい答えの比較を見ました。 n=4
出力[{1,#,2,#,3,#,4},{1,#,2,#,4,3},{1,#,3,2,4},{1,#,4,2,#,#,3},{1,#,4,3,#,2},{2,1,3,#,#,#,4},{2,1,4,#,#,3},{3,2,4,1},{4,1,#,#,2,#,3},{4,1,#,#,3,2},{4,2,#,1,3},{4,3,#,1,#,#,2},{4,3,#,2,#,1}]
答えを期待する[{1,#,2,#,3,#,4},{1,#,2,#,4,3},{1,#,3,2,4},{1,#,4,2,#,#,3},{1,#,4,3,#,2},{2,1,3,#,#,#,4},{2,1,4,#,#,3},{3,1,4,#,2},{3,2,4,1},{4,1,#,#,2,#,3},{4,1,#,#,3,2},{4,2,#,1,3},{4,3,#,1,#,#,2},{4,3,#,2,#,1}]
つまり、少なくなりました。{3,1,4,シ、2}3を根っこにしている二叉の木がなぜ少なくなりましたか?よく考えてみると、3点の左の子供は1でもいいし、2でもいいです。左の子供は1の場合は無視されます。この時はuseNodeはnに等しくないです。左の子供は2点になります。正しいコード:
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @paramn n: An integer
* @return: A list of root
*/
vector buildT(int ld, int rd){
vector ans;
if(ld == rd) {
TreeNode *T = new TreeNode(ld);
ans.push_back(T);
return ans;
}
if(ld > rd){
ans.push_back(NULL);
return ans;
}
for(int i=ld; i<=rd; ++i){
vector ansLeft = buildT(ld, i-1);
vector ansRight = buildT(i+1, rd);
for(auto lx : ansLeft)
for(auto rx : ansRight){
TreeNode *T = new TreeNode(i);
T->left = lx;
T->right = rx;
ans.push_back(T);
}
}
return ans;
}
vector generateTrees(int n) {
// write your code here
vector ans = buildT(1, n);
return ans;
}
};
分析:現在の結点Xを確定した後、Xの左の子供の結点(または右の子供の結点)が複数あるかもしれないので、これらの可能な結点を全部vectorに預けて、左の子供の集合からlx結点を選んで、右の子供の集合からrx結点を選んでください。転載先:https://www.cnblogs.com/hujunzheng/p/5040334.html