花花酱 LeetCode 95. Unique Binary Search Trees II

By zxi on March 7, 2018

Problem

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

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

Idea: Recursion

for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)

# of trees:

n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132
…
Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)

Time complexity: O(3^n)

Space complexity: O(3^n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<TreeNode*> generateTrees(int n) {

if (n == 0) return {};

const auto& ans = generateTrees(1, n);

cout << ans.size() << endl;

return ans;

}

private:

vector<TreeNode*> generateTrees(int l, int r) {

if (l > r) return { nullptr };

vector<TreeNode*> ans;

for (int i = l; i <= r; ++i)

for (TreeNode* left : generateTrees(l, i - 1))

for (TreeNode* right : generateTrees(i + 1, r)) {

ans.push_back(new TreeNode(i));

ans.back()->left = left;

ans.back()->right = right;

}

return ans;

}

};

Java

// Author: Huahua 4 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

return generateTrees(1, n);

}

private List<TreeNode> generateTrees(int l, int r) {

List<TreeNode> ans = new ArrayList<>();

if (l > r) {

ans.add(null);

return ans;

}

for (int i = l; i <= r; ++i)

for (TreeNode left : generateTrees(l, i - 1))

for (TreeNode right: generateTrees(i + 1, r)) {

TreeNode root = new TreeNode(i);

root.left = left;

root.right = right;

ans.add(root);

}

return ans;

}

Python 3

"""

Author: Huahua

Running time: 84 ms

"""

class Solution:

def generateTrees(self, n):

def newTree(x, l, r):

t = TreeNode(x)

t.left = l

t.right = r

return t

def gen(s, e):

return [newTree(i, l, r) for i in range(s, e + 1) for l in gen(s, i - 1) for r in gen(i + 1, e)] or [None]

return gen(1, n) if n > 0 else []

Solution 2: DP

Java

// Author: Huahua, 3 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

List<TreeNode>[] dp = new List[n + 1];

dp[0] = new ArrayList<TreeNode>();

dp[0].add(null);

for (int i = 1; i <= n; ++i) {

dp[i] = new ArrayList<TreeNode>();

for (int j = 0; j < i; ++j)

for (TreeNode left : dp[j])

for (TreeNode right: dp[i - j - 1]) {

TreeNode root = new TreeNode(j + 1);

root.left = left;

root.right = clone(right, j + 1);

dp[i].add(root);

}

return dp[n];

}

private TreeNode clone(TreeNode root, int delta) {

if (root == null) return root;

TreeNode node = new TreeNode(root.val + delta);

node.left = clone(root.left, delta);

node.right = clone(root.right, delta);

return node;

}

Problem:

https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

Solution 1: Recursion

Time complexity: O(log5(n))

Space complexity: O(log5(n))

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

public int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

Python3

"""

Author: Huahua

Running time: 68 ms

"""

class Solution:

def trailingZeroes(self, n):

return 0 if n < 5 else n // 5 + self.trailingZeroes(n // 5)

花花酱 LeetCode 95. Unique Binary Search Trees II

Problem

Idea: Recursion

C++

Java

Python 3

Solution 2: DP

Java

Related Problems

花花酱 LeetCode 620. Not Boring Movies

花花酱 LeetCode 15. 3Sum

花花酱 LeetCode 172. Factorial Trailing Zeroes

Problem:

Idea:

Solution 1: Recursion

C++

Java

Python3

Related Problems:

花花酱 LeetCode 696. Count Binary Substrings

Huahua's Tech Road

花花酱 LeetCode 95. Unique Binary Search Trees II

Problem

Idea: Recursion

C++

Java

Python 3

Solution 2: DP

Java

Related Problems

花花酱 LeetCode 620. Not Boring Movies

花花酱 LeetCode 15. 3Sum

花花酱 LeetCode 172. Factorial Trailing Zeroes

Problem:

Idea:

Solution 1: Recursion

C++

Java

Python3

Related Problems:

花花酱 LeetCode 696. Count Binary Substrings