Leetcode: Unique Binary Search Trees II

Unique Binary Search Trees II



Similar Problems:


Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   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.


// Blog link: https://code.dennyzhang.com/unique-binary-search-trees-ii
// Basic Ideas: dynamic programming
// f(i):
//         j+1
//       /  \
//      /    \
//   f(j)    f(i-j-1)
// For the right subtree, add j+1 to the value of each node
//
// Complexity: Time O(2^n), Space O(2^n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func deepCopyWithAdd(root *TreeNode, v int) *TreeNode {
    if root == nil { return nil }
    res := &TreeNode{root.Val+v, nil, nil}
    res.Left, res.Right = deepCopyWithAdd(root.Left, v), deepCopyWithAdd(root.Right, v)
    return res
}

func generateTrees(n int) []*TreeNode {
    if n<=0 { return []*TreeNode{}}
    l := [][]*TreeNode{}
    l = append(l, []*TreeNode{nil})
    l = append(l, []*TreeNode{&TreeNode{1, nil, nil}})
    for i:=2; i<=n; i++ {
        l2 := []*TreeNode{}
        for j:=0; j<i; j++ {
            for _, left := range l[j] {
                for _, right := range l[i-j-1] {
                    parent := &TreeNode{j+1, deepCopyWithAdd(left, 0), deepCopyWithAdd(right, j+1)}
                    l2 = append(l2, parent)
                }
            }
        }
        l = append(l, l2)
    }
    return l[n]
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.