[LeetCode]题解（python）：096-Unique Binary Search Trees

题目来源：

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

题意分析：

　　给定一个整数n，返回所有中序遍历是1到n的树的可能。

题目思路：

　　这是动态规划的题目。选定了第k个为根节点，那么所有的可能就是ans[k-1] * ans[n -k]其中，ans[i]代表i整数i一共有ans[i]种可能。

代码（python）：

class Solution(object):

    def numTrees(self, n):

        """

        :type n: int

        :rtype: int

        """

        ans = [0 for i in range(n + 1)]

        ans[0],ans[1] = 1,1

        for i in range(2,n+1):

            for j in range(i/2):

                ans[i] += ans[j]*ans[i - 1 - j]

            ans[i] *= 2

            if i % 2 == 1:

                ans[i] += ans[i/2]*ans[i/2]

        return ans[n]

巴特西

[LeetCode]题解（python）：096-Unique Binary Search Trees

最新文章

热门文章