[Leetcode Solution] Unique Binary Search Trees

GOOD PROBLEM

Analysis

• Good problem with tricky idea behind it. Once read this problem one year ago at data structure course but a specific size of n which I solved by handy building up all the unique trees. Today focus this problem I still didn't figure out the solution myself.
• Build up the binary tree with the same array of numbers but in different order will resulting into different trees.
• Given a sequence with n elements in ascending order to build the binary tree. If we choose i-th elements as the root of the tree, then the problem will be reduced into two sub-problems which aim build up a binary tree with a sequence in ascending order with length of i-1 and n-i separately. This is the key trick of this problem which implies us solving the problem by dynamic programming without doubt
• Let f[n] denote the number of unique binary trees can be built with a sequence with length of n. Then
• f[n] = f[i-1]*f[n-i] (0<=i<=n)

Note

Code

UPDATED AT 3rd PASS