95. Unique Binary Search Trees II

发布时间：2020-12-14 04:30:35 所属栏目：大数据来源：网络整理

导读：1. Question: 95.?Unique Binary Search Trees II Given an integer? n ,generate all structurally unique?BST‘s?(binary search trees) that store values 1 ...? n . Example: Input: 3Output:[? [1,null,3,2],? [3,2,1],1,? [2,3],? [1,3]]Explanation:

1. Question:

95.?Unique Binary Search Trees II

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

Example:

Input: 3
Output:
[
? [1,null,3,2],? [3,2,1],1,? [2,3],? [1,3]
]
Explanation:
The above output corresponds to the 5 unique BST‘s shown below:

   1         3     3      2      1
           /     /      /            3     2     1      1   3      2
    /     /                           2     1         2                 3

2. Solution:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):

    def genTrees(self,values):
        size = len(values)
        if size <= 0:
            return []
        re_list = []

        if size == 1:
            node = TreeNode(values[0])
            re_list.append(node)
            return re_list

        for i in range(size):
            left_list = self.genTrees(values[:i])
            right_list = self.genTrees(values[i + 1:])

            if len(left_list) == 0:
                for right in right_list:
                    root = TreeNode(values[i])
                    root.right = right
                    re_list.append(root)
                continue

            if len(right_list) == 0:
                for left in left_list:
                    root = TreeNode(values[i])
                    root.left = left
                    re_list.append(root)
                continue

            for left in left_list:
                for right in right_list:
                    root = TreeNode(values[i])
                    root.left = left
                    root.right = right
                    re_list.append(root)

        return re_list

    def generateTrees(self,n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        re_list = []

        if n == 1:
            root = TreeNode(1)
            re_list.append(root)
            return re_list

        for value in range(1,n + 1):
            left_list = self.genTrees(list(range(1,value)))
            right_list = self.genTrees(list(range(value + 1,n + 1)))

            if len(left_list) == 0:
                for right in right_list:
                    root = TreeNode(value)
                    root.right = right
                    re_list.append(root)
                continue

            if len(right_list) == 0:
                for left in left_list:
                    root = TreeNode(value)
                    root.left = left
                    re_list.append(root)
                continue

            for left in left_list:
                for right in right_list:
                    root = TreeNode(value)
                    root.left = left
                    root.right = right
                    re_list.append(root)

        return re_list


if __name__ == "__main__":
    obj = Solution()
    re = obj.generateTrees(3)
    print(re)
    print("Done")

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!