Given 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
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1 / 2 3 / 4 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.96. Unique Binary Search Trees 的扩展,96题只要算出所有不同BST的个数,这道题让把那些二叉树都表示出来。
用递归来解,划分左右子树,递归构造。
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而组成一颗新树。
Python:
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 唯一二叉搜索树