[LeetCode] 95. Unique Binary Search Trees II 惟一二叉搜索树 II

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 95. Unique Binary Search Trees II 惟一二叉搜索树 II,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.html

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

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.python

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.app

Here's an example:post

   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as  "{1,2,3,#,#,4,#,#,5}".

96. Unique Binary Search Trees 的扩展,96题只要算出全部不一样BST的个数,这道题让把那些二叉树都表示出来。url

用递归来解,划分左右子树,递归构造。code

1. 根节点能够任取min ~ max (例如min = 1, max = n),假如取定为i。
2. 则left subtree由min ~ i-1组成,假设能够有L种可能。right subtree由i+1 ~ max组成,假设有R种可能。生成全部可能的left/right subtree。
3 对于每一个生成的left subtree/right subtree组合<T_left(p), T_right(q)>,p = 1...L,q = 1...R,添加上根节点i而组成一颗新树。htm

Python:blog

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
    def __repr__(self):
        if self:
            serial = []
            queue = [self]

            while queue:
                cur = queue[0]
                
                if cur:
                    serial.append(cur.val)
                    queue.append(cur.left)
                    queue.append(cur.right)
                else:
                    serial.append("#")
                
                queue = queue[1:]
                
            while serial[-1] == "#":
                serial.pop()
                
            return repr(serial)
                
        else:
            return None

class Solution:
    # @return a list of tree node
    def generateTrees(self, n):
        return self.generateTreesRecu(1, n)
    
    def generateTreesRecu(self, low, high):
        result = []
        if low > high:
            result.append(None)
        for i in xrange(low, high + 1):
            left = self.generateTreesRecu(low, i - 1)
            right = self.generateTreesRecu(i + 1, high)
            for j in left:
                for k in right:
                    cur = TreeNode(i)
                    cur.left = j
                    cur.right = k
                    result.append(cur)
        return result

C++:递归

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return genBST(1, n);
    }
    
    vector<TreeNode *> genBST(int min, int max) {
        vector<TreeNode *> ret;
        if(min>max) {
            ret.push_back(NULL);
            return ret;
        }
        
        for(int i=min; i<=max; i++) {
            vector<TreeNode*> leftSubTree = genBST(min,i-1);
            vector<TreeNode*> rightSubTree = genBST(i+1,max);
            for(int j=0; j<leftSubTree.size(); j++) {
                for(int k=0; k<rightSubTree.size(); k++) {
                    TreeNode *root = new TreeNode(i);
                    root->left = leftSubTree[j];
                    root->right = rightSubTree[k];
                    ret.push_back(root);
                }
            }
        }
        
        return ret;
    }
};

 

相似题目:

[LeetCode] 96. Unique Binary Search Trees 惟一二叉搜索树 

 

All LeetCode Questions List 题目汇总