教怎么做糕点网站/网站搭建平台

前置知识

• BST，就是我们平时说的平衡二叉树。这种树的性质是对于节点root，root左边的所有的子节点的权值都小于这个root的权值，root右边所有子树的权值都大于root的权值。

BST构建的两种方法

递归实现

• 这种实现方法一般比较方便，思维含量也相对较低。就是根据树的可递归的性质，我们对树进行递归构建，从根开始向叶子结点进行构建，我们利用二分的方法进行处理，当前边界二分之后的终点的权值就是我们当前这个结点的权值了。

• 代码如下

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;* };*/class Solution {
public:/*** * @param num int整型vector * @return TreeNode类*/TreeNode* createTree(int l,int r,vector<int>& num){// 递归的边界if(l>r){return NULL;}// 先求中点int mid=(l+r)>>1;TreeNode* now = new TreeNode(num[mid]);now->left=createTree(l,mid-1,num);  // 递归构建左子树now->right=createTree(mid+1,r,num);  // 递归构建右子树return now;}TreeNode* sortedArrayToBST(vector<int>& num) {// 特判空结点的情况if(num.size()==0){return NULL;}return createTree(0,num.size()-1,num);}
};

非递归实现

• 递归的方法相信很多人都会了，但是对于非递归的方法，一般是比较难想到的。
• 对于非递归的方法，我们一般是采用队列来进行处理，为什么呢？这里我们可以这么理解。我们在进行递归处理的时候，我们发现，我们是先处理完当前这个结点，然后递归到这个结点的左右结点进行处理。先递归到的就先进行处理，这与我们那个数据结构能进行关联呢？对的，就是队列，学过数据结构的同学都知道，队列的性质就是先进先出。那么我们完全可以将我们每次递归需要的参数都放到队列里面，然后按照队列里面元素的先后顺序进行处理，这样，不久可以达到和递归相同的处理了吗？而且我们这种方法不需要使用真的递归，显然是更好的方法。
• 这里，我们需要用到的是结点指针和左右边界，由于他们的参数类型不一样，所以这里我们使用两个队列来进行处理。
• 所以，这其实就是一个很经典的BFS模型了，我们先将初始参数放进队列里面，然后，我们一步一步进行拓展即可。

• 代码如下

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;* };*/class Solution {
public:/*** * @param num int整型vector * @return TreeNode类*/TreeNode* sortedArrayToBST(vector<int>& num) {// write code hereif(num.size()==0){return NULL;}queue<TreeNode*> st_node;queue<int> st_index;// 初始化根节点TreeNode* root = new TreeNode(0);st_node.push(root);st_index.push(0);st_index.push(num.size()-1);while(!st_node.empty()){// 取出当前这一层结点处理我们需要的参数，主要是左右边界int l=st_index.front();st_index.pop();int r=st_index.front();st_index.pop();int mid=(l+r)>>1;TreeNode* now = st_node.front();st_node.pop();now->val=num[mid];// 拓展左子节点处理需要的参数if(l<mid){st_index.push(l);st_index.push(mid-1);TreeNode* tmp = new TreeNode(0);root->left=tmp;st_node.push(tmp);}// 拓展右子节点处理需要的参数if(r>mid){st_index.push(mid+1);st_index.push(r);TreeNode* tmp = new TreeNode(0);root->right=tmp;st_node.push(tmp);}}return root;}
};