CODEWITHSUNDEEP
c++algorithmc++11binary-tree
Ink
Ink

Reputation: 963

What's wrong with my build binary tree solution?

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

Answers (2)

Travis
Travis

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

cedrou
cedrou

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

Related Questions