欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

105. Construct Binary Tree from Preorder and Inorder Traversal

程序员文章站 2022-03-03 10:13:11
...

这道题用指针,分治思想,相信看代码就能很容易弄懂了

这里有一个问题未解决(希望有人可以回答一下:
buildTree函数如果不加if语句在input为两个空vector对象的时候报错,搞不清楚为什么,因为我的build函数里是有对这个的判断的,两个空对象的时候进去p_l-p_r>0条件应该成立才对,也就是返回NULL,且我在本地环境运行无问题
错误为:Line 842: Char 45: runtime error: pointer index expression with base 0x000000000000 overflowed to 0xfffffffffffffffc (stl_iterator.h)

class Solution {
public:
    TreeNode* build(vector<int>::iterator p_l,vector<int>::iterator p_r,
        vector<int>::iterator i_l,vector<int>::iterator i_r){
        if(p_l-p_r>0)return NULL;
        TreeNode* current=new TreeNode(*p_l);
        auto k=find(i_l,i_r,current->val);
        int left_tree_n=k-i_l;
        current->left=build(p_l+1,p_l+left_tree_n,i_l,k-1);
        current->right=build(p_l+left_tree_n+1,p_r,k+1,i_r);
        return current;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())return NULL;
        return build(preorder.begin(),preorder.end()-1,inorder.begin(),inorder.end()-1);
    } 
};