FilesExpand file tree

 master

/

leetcode95Or96.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

61 lines (55 loc) · 1.56 KB

 master

/

leetcode95Or96.java

Top

File metadata and controls

• Code
• Blame

61 lines (55 loc) · 1.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

package leetcode.dp;

import leetcode.tree.TreeNode;

import java.util.LinkedList;

import java.util.List;

/*

* 卡特兰数的计算方法

* */

public class leetcode95Or96 {

/*

* 96

* */

public int numTrees(int n) {

int []G=new int[n+1];

G[0]=1;

G[1]=1;

for (int i = 2; i <=n; i++) {

for (int j = 1; j <=i ; j++) {

G[i]+=G[j-1]*G[i-j];

}

}

return G[n];

}

/*

* 95

* */

public List<TreeNode> generateTrees(int n) {

if (n == 0) {

return new LinkedList<TreeNode>();

}

return generate_trees(1, n);

}

/*

* start-end 生成子树

* */

public LinkedList<TreeNode> generate_trees(int start, int end) {

LinkedList<TreeNode> all_trees = new LinkedList<TreeNode>(); //存储所有可能子树的根节点

if (start>end){

all_trees.add(null);

return all_trees;

}

for (int i=start;i<=end;i++){

LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);

LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);

for (TreeNode l : left_trees) {

for (TreeNode r : right_trees) {

TreeNode current_tree = new TreeNode(i);

current_tree.left = l;

current_tree.right = r;

all_trees.add(current_tree); //以i节点为跟节点的所有可能的子树

}

}

}

return all_trees; //返回子树

}

}