Reputation: 963
I tried to build a binary tree condition on its preorder and inorder traversal.
However, when I ran the code below, 20% test samples passed then I got "1351 segmentation fault (core dumped)" with preorder = inorder = {1,2}.
What wrong with my code? And how to debug the "segmentation fault" on linux?
THANKS!!!
class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
// write your code here
TreeNode * root;
if (preorder.empty() || inorder.empty()) {
cout<<"in if"<<endl;
return NULL;
}
root->val = preorder.front();
vector<int> inorder_left(inorder.begin(), inorder.begin() + getIndex(inorder, preorder.front()));
vector<int> inorder_right(inorder.begin() + getIndex(inorder, preorder.front()) + 1, inorder.end());
vector<int> preorder_left(preorder.begin() + 1, preorder.begin() + 1 + inorder_left.size());
vector<int> preorder_right(preorder.begin() + 1 + inorder_left.size(), preorder.end());
root->left = buildTree(preorder_left, inorder_left);
root->right = buildTree(preorder_right, inorder_right);
return root;
}
private:
int getIndex(vector<int> & vec, int target) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == target) {
return i;
}
}
}
};
Upvotes: 0
Views: 91
Reputation: 55
root
isn't actually initialized to a value.
You declare it:
TreeNode *root;
...but then you need to initialize it, like this:
root = new TreeNode;
Upvotes: 3
Reputation: 2790
The pointer root
is not initialized when you access its members val
, left
and right
. Initialize it with new TreeNode()
for example.
Upvotes: 5