FilesExpand file tree

 master

/

_096UniqueBinarySearchTrees.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

34 lines (33 loc) · 1.04 KB

 master

/

_096UniqueBinarySearchTrees.java

Copy path

Top

File metadata and controls

• Code
• Blame

34 lines (33 loc) · 1.04 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

/**

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

* <p>

* For example,

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

* <p>

* 1 3 3 2 1

* \ / / / \ \

* 3 2 1 1 3 2

* / / \ \

* 2 1 2 3

* <p>

* Created by drfish on 27/05/2017.

*/

public class _096UniqueBinarySearchTrees {

public int numTrees(int n) {

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

counts[0] = 1;

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

int count = 0;

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

count += counts[j] * counts[i - 1 - j];

}

counts[i] = count;

}

return counts[n];

}

public static void main(String[] args) {

_096UniqueBinarySearchTrees uniqueBinarySearchTrees = new _096UniqueBinarySearchTrees();

assert uniqueBinarySearchTrees.numTrees(3) == 5;

assert uniqueBinarySearchTrees.numTrees(6) == 132;

}

}