Unique BST C#


  • 0
    P
    public class Solution {
            public int NumTrees(int n)
            {
                int[] memo = new int[n + 1];
                return subTrees(n, memo);
            }
    
            private int subTrees(int totalNum, int[] memo)
            {
                if (totalNum == 0) return 1;
                if (totalNum == 1) return 1;
    
                int sum = 0;
                for (int iter = 0; iter < totalNum; iter++)
                {
                    int leftTreeLength = iter;
                    int rightSubTreeLength = totalNum - iter - 1;
    
                    if(memo[leftTreeLength] == 0)
                    {
                        memo[leftTreeLength] = subTrees(leftTreeLength, memo);
                    }
    
                    if (memo[rightSubTreeLength] == 0)
                    {
                        memo[rightSubTreeLength] = subTrees(rightSubTreeLength, memo);
                    }
    
                    sum += memo[leftTreeLength] * memo[rightSubTreeLength];
                }
    
                return sum;
            }
    }
    

Log in to reply
 

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