Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
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
题解
题 Unique Binary Search Trees 的升级版,这道题要求的不是二叉搜索树的数目,而是要构建这样的树。分析方法仍然是可以借鉴的,核心思想为利用『二叉搜索树』的定义,如果以 i 为根节点,那么其左子树由[1, i - 1]构成,右子树由[i + 1, n] 构成。要构建包含1到n的二叉搜索树,只需遍历1到n中的数作为根节点,以i为界将数列分为左右两部分,小于i的数作为左子树,大于i的数作为右子树,使用两重循环将左右子树所有可能的组合链接到以i为根节点的节点上。
// dfs for (int i = start; i <= end; ++i) { leftTree = helper(start, i - 1); rightTree = helper(i + 1, end); // link left and right sub tree to the root i for (j in leftTree ){ for (k in rightTree) { root = TreeNode(i); root->left = leftTree[j]; root->right = rightTree[k]; result.push_back(root); } } }
""" Definition of TreeNode: class TreeNode: def __init__(self, val): this.val = val this.left, this.right = None, None """ classSolution: # @paramn n: An integer # @return: A list of root defgenerateTrees(self, n): return self.helper(1, n)
defhelper(self, start, end): result = [] if start > end: result.append(None) return result
for i in xrange(start, end + 1): # generate left and right sub tree leftTree = self.helper(start, i - 1) rightTree = self.helper(i + 1, end) # link left and right sub tree to root(i) for j in xrange(len(leftTree)): for k in xrange(len(rightTree)): root = TreeNode(i) root.left = leftTree[j] root.right = rightTree[k] result.append(root)
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ classSolution { public: /** * @paramn n: An integer * @return: A list of root */ vector<TreeNode *> generateTrees(int n){ returnhelper(1, n); }
private: vector<TreeNode *> helper(int start, int end){ vector<TreeNode *> result; if (start > end) { result.push_back(NULL); return result; }
for (int i = start; i <= end; ++i) { // generate left and right sub tree vector<TreeNode *> leftTree = helper(start, i - 1); vector<TreeNode *> rightTree = helper(i + 1, end); // link left and right sub tree to root(i) for (int j = 0; j < leftTree.size(); ++j) { for (int k = 0; k < rightTree.size(); ++k) { TreeNode *root = newTreeNode(i); root->left = leftTree[j]; root->right = rightTree[k]; result.push_back(root); } } }
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ publicclassSolution { /** * @paramn n: An integer * @return: A list of root */ public List<TreeNode> generateTrees(int n) { return helper(1, n); }
private List<TreeNode> helper(int start, int end) { List<TreeNode> result = newArrayList<TreeNode>(); if (start > end) { result.add(null); return result; }
for (inti= start; i <= end; i++) { // generate left and right sub tree List<TreeNode> leftTree = helper(start, i - 1); List<TreeNode> rightTree = helper(i + 1, end); // link left and right sub tree to root(i) for (TreeNode lnode: leftTree) { for (TreeNode rnode: rightTree) { TreeNoderoot=newTreeNode(i); root.left = lnode; root.right = rnode; result.add(root); } } }