LeetCode 1008. 先序遍历构造二叉树（已知先序，求二叉搜索树）

Michael阿明

发布于 2021-02-19 22:24:35

7570

发布于 2021-02-19 22:24:35

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

文章目录
1. 题目
2. 解题

1. 题目

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

示例：

输入：[8,5,1,7,10,12]，已知二叉搜索树的先序（根左右）
输出：[8,5,10,1,7,null,12]，建立二叉搜索树，返回其root

2. 解题

办法1：排序后就是搜索树的中序，那已知先序和中序，可唯一确定树

办法2：利用二叉搜索树的性质，左子树所有的值都小于root，右子树都大于root
在先序里第一个是根节点的值，然后后面跟着的比它小的是左子树，有大的出现了，就是右子树部分的
递归进行上面步骤

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return form(preorder,0,preorder.size()-1);
    }
    
    TreeNode* form(vector<int>& preorder, int start, int end)
    {
    	if(start > end)
    		return NULL;
    	TreeNode* newroot = new TreeNode(preorder[start]);
        int i;
    	for(i = start+1; i <= end; ++i)
    	{
    		if(preorder[i] > preorder[start])
    			break;//右子树的开始 i 
    	}
    	newroot->left = form(preorder,start+1,i-1);
    	newroot->right = form(preorder,i,end);
 		return newroot;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-09-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

binary