这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » unique-binary-search-trees-ii

共2条 1/1 1 跳转至

unique-binary-search-trees-ii

高工
2018-01-13 21:08:12     打赏

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.


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.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

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


题意:输出1到n组成的所有二叉搜索树的结构

思路:

选定1-n的一个数字i作为根节点、0到i-1是左子树, i+1-n是右子树,两层循环;


[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.     vector<TreeNode*> generateTrees(int n)  

  5.     {  

  6.         return create(1, n);  

  7.     }  

  8.   

  9.     vector<TreeNode*> create(int left, int right)  

  10.     {  

  11.         vector<TreeNode*> res;  

  12.         if (left>right)  

  13.         {  

  14.             res.push_back(NULL);  

  15.             return res;  

  16.         }  

  17.   

  18.         for (int i=left; i<=right; i++)  

  19.         {  

  20.             vector<TreeNode*> leftTree = create(left, i-1);  

  21.             vector<TreeNode*> rightTree = create(i+1, right);  

  22.   

  23.             for (int j = 0; j<leftTree.size(); j++)  

  24.             {  

  25.                 for (int k = 0; k<rightTree.size(); k++)  

  26.                 {  

  27.                     TreeNode* root = new TreeNode(i);  

  28.                     root->left = leftTree[j];  

  29.                     root->right = rightTree[k];  

  30.   

  31.                     res.push_back(root);  

  32.                 }  

  33.             }  

  34.         }  

  35.   

  36.         return res;  

  37.     }  

  38. };




专家
2018-01-14 11:04:11     打赏
2楼

谢谢分享源码。


共2条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]