LeetCode: Unique Binary Search Trees Posted on January 20, 2018July 26, 2020 by braindenny Unique Binary Search Trees Similar Problems: LeetCode: Unique Binary Search Trees II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #binarytree, #dynamicprogramming, #fibonacci Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: dp ## https://code.dennyzhang.com/unique-binary-search-trees ## Basic Ideas: dynamic programming ## ## dp(i): count with i nodes ## ## There must be one root node ## ## dp(j)*dp(i-1-j) ## j = 0...i-1 ## Complexity: Time O(n*n), Space O(1) class Solution: def numTrees(self, n: int) -> int: dp = [0]*(n+1) dp[0] = 1 for i in range(1, n+1): for j in range(i): dp[i] += dp[j]*dp[i-1-j] return dp[-1] Solution: dp // https://code.dennyzhang.com/unique-binary-search-trees // Basic Ideas: dynamic programming // Pitfalls: try to compare the values. This direction will make things very complicated // // How to get f(n) from previous values? // 1. We will have a root, so sum(left sub-tree nodes) + sum(right sub-tree nodes) = n-1 // 2. If root is i, left sub-tree will have i-1 nodes, right sub-tree will have n-k nodes. // How many different types? f(i-1)*f(n-i) // 3. Loop k from 1 to n. Then collect the total number // n = 2: // // 1 2 // \ / // 2 1 // // n = 3: // // 1 3 3 2 1 // \ / / / \ \ // 3 2 1 1 3 2 // / / \ \ // 2 1 2 3 // // n = 4: // // // // Complexity: func numTrees(n int) int { if n<=1 {return n} dp := make([]int, n+1) dp[0] = 1 for i, _:= range dp { if i == 0 { continue } for j := 0; j<i; j++ { dp[i] += dp[j]*dp[i-1-j] } } return dp[n] } Post Views: 8 Post navigation LeetCode: Subsets IILeetCode: Delete Node in a BST Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website