郑州官网网站推广优化,工程门户网站建设,wordpress建站的好处,代理平台什么意思文章目录1. 题目2. 解题1. 题目
返回与给定先序遍历 preorder 相匹配的二叉搜索树#xff08;binary search tree#xff09;的根结点。
示例#xff1a;输入#xff1a;[8,5,1,7,10,12]#xff0c;已知二叉搜索树的先序#xff08;根左右#xff09;
输出#xff1a…
文章目录1. 题目2. 解题1. 题目
返回与给定先序遍历 preorder 相匹配的二叉搜索树binary search tree的根结点。
示例输入[8,5,1,7,10,12]已知二叉搜索树的先序根左右
输出[8,5,10,1,7,null,12]建立二叉搜索树返回其root2. 解题
办法1排序后就是搜索树的中序那已知先序和中序可唯一确定树 办法2利用二叉搜索树的性质左子树所有的值都小于root右子树都大于root在先序里第一个是根节点的值然后后面跟着的比它小的是左子树有大的出现了就是右子树部分的递归进行上面步骤
class Solution {
public:TreeNode* bstFromPreorder(vectorint preorder) {return form(preorder,0,preorder.size()-1);}TreeNode* form(vectorint preorder, int start, int end){if(start end)return NULL;TreeNode* newroot new TreeNode(preorder[start]);int i;for(i start1; i end; i){if(preorder[i] preorder[start])break;//右子树的开始 i }newroot-left form(preorder,start1,i-1);newroot-right form(preorder,i,end);return newroot;}
};
