题目描述
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
示例：
输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
解法
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
int len;
if ((len= preorder.size())==0) {
return nullptr;
}
return buildBST(preorder, 0, len - 1);
}
TreeNode* buildBST(vector<int>& preorder,int left,int right) {
if (left > right) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[left]);
if (left == right) {
return root;
}
int i = left;
while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
i++;
}
TreeNode* leftTree = buildBST(preorder, left + 1, i);
TreeNode* rightTree = buildBST(preorder, i + 1, right);
root->left = leftTree;
root->right = rightTree;
return root;
}
};
解题思路
递归
涉及到二叉树先考虑递归再说，递归大致结构体
{
if(条件体){
//结束判断
return null;
}
if(条件体){
//返回值
return 返回值;
}
1、赋值
2、返回结果
}
然后分析题目的例子，前序遍历构建二叉搜索树
1、二叉搜索树的特点，左小右大
2、前序遍历的特点，第一个数就是根节点
根据以上的特点，我们可以将前序遍历分成两个部分或者说三个部分
1、根节点|左子树|右子树，其中root>左子树的值，root<右子树的值
//找到右子树的节点
int i = left;
while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
i++;
}
找到右子树的节点后，就可以递归构建左右子树
//left就是根节点，left+1就是左子树的节点
TreeNode* leftTree = buildBST(preorder, left + 1, i);
TreeNode* rightTree = buildBST(preorder, i + 1, right);
root->left = leftTree;
root->right = rightTree;
return root;
再完善递归的结束判断和赋值，采用分治的思路，
如果不看8的根节点，5节点是1和7的根节点；10是12的根节点，依次类推，每个节点都是“根节点”
TreeNode* buildBST(vector<int>& preorder,int left,int right) {
if (left > right) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[left]);
//左右指针相等时，则是根节点，返回结果
if (left == right) {
return root;
}
int i = left;
while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
i++;
}
TreeNode* leftTree = buildBST(preorder, left + 1, i);
TreeNode* rightTree = buildBST(preorder, i + 1, right);
root->left = leftTree;
root->right = rightTree;
return root;
}