不同的二叉查找树

yingl · yingl · commit 0544b80ec9aa · 2016-09-23T14:58:03.000+08:00
diff --git a/unique_binary_search_trees.py b/unique_binary_search_trees.py
@@ -1,25 +1,14 @@
-# -*- coding: utf-8 -*-
-
 class Solution:
-    def __init__(self):
-        self.cache = {}
-
     # @paramn n: An integer
     # @return: An integer
     def numTrees(self, n):
-        if n <= 1:
+        # write your code here
+        # 只需要计算数量，不需要计算每棵树的形状，所以缓存结果就可以了。
+        if n == 0:
             return 1
-        else:
-            if n in self.cache:
-                return self.cache[n]
-            else:
-                sum = 0
-                for i in xrange(1, n + 1):
-                    left_num, right_num = 1, 1
-                    if i > 0:
-                        left_num = self.numTrees(i - 1) # 计算左子树数量
-                    if i < n:
-                        right_num = self.numTrees(n - i)  # 计算右子树数量
-                    sum += left_num * right_num
-                self.cache[n] = sum
-        return self.cache[n]
+        methods = [0] * (n + 1)
+        methods[0], methods[1] = 1, 1
+        for i in xrange(2, n + 1):
+            for j in xrange(1, i + 1):
+                methods[i] += methods[j - 1] * methods[i - j]
+        return methods[-1]
