Solution by jamesyang2333


  • 1
    J

    Approach #1 Dynamic Programming [Accepted]

    Intuition

    As the number of unique binary search trees only depends on the total number of nodes, i.e. it is independent of node values, we could calculate the number of unique binary search trees using recursive relation.

    Algorithm

    Suppose the function f ( n ) is defined to be the number of unique binary search trees containing n nodes from 1 to n. Then we could calculate f ( n ) in the following way:

    if the root node is 1, its left subtree is empty, so there is only one way to construct the left subtree; its right subtree has size n - 1, so there are f ( n - 1 ) ways to construct the right subtree. Therefore, there are f ( n - 1 ) unique binary search trees.

    if the root node is 2, through the same reasoning, there are f ( 1 ) ways to construct the right subtree and f ( n - 2 ) ways to construct the right subtree, so there are f ( 1 ) * f ( n - 2 ) unique binary search trees.

    ......

    if the root node is n, there are f ( n - 1 ) ways to construct the left subtree and one way to construct the right subtree, which is empty, so there are f ( n - 1 ) unique binary search trees.

    Now, by adding all the cases up, we could derive the recursive relation as follows: f ( n ) = ∑ f ( i ) * f ( n - 1 - i ), where i is from 0 to n - 1. Note that we define f ( 0 ) = 1, as there's only one way to construct an empty tree.

    To implement the solution, we could use an iterative Dynamic Programming approach. We maintain an integer array dp[ ], where dp[ i ] corresponds to the number of unique binary search trees containing i nodes. By iterating through case 2 to n, we could find the answer really fast.

    In addition, the number of unique binary search trees containing 1 to n is actually equal to Catalan number Cn, a important number in combinatorics. A detailed explanation of Catalan number could be found here.

    Java

    class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                int result = 0;
                for(int j = 0; j < i; j++){
                    result += (dp[j] * dp[i - 1 - j]);
                }
                dp[i] = result;
            }
            return dp[n];
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n^2).

    At iteration i, we calculate i cases with different root node values, which leads to a time complexity of O(n). As there's a total of n - 1 iterations, the overall time complexity is O(n^2).

    • Space complexity : O(n). We maintain the integer array dp[ ] of size n.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.