Michelle Shieh Michelle Shieh - 2 months ago 11
C++ Question

Why the node value changed when get out of the function?

I am trying to build a binary tree(no duplicate) with its preorder and ignorer sequence in C++.

The coding is as following:

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x),left(NULL),right(NULL) {}
};

int idx = 0; //idx in preorder
void helper(TreeNode* node,int start,int end, vector<int>& preorder, vector<int>& inorder) {
if (start == end) return;
int dummy;
for (dummy = 0; dummy<inorder.size(); dummy++) {
if (inorder[dummy] == node->val) {
break;
}
}
idx ++;
TreeNode left = TreeNode(preorder[idx]);
node->left = &left;
helper(node->left,start,dummy-1,preorder,inorder);
idx ++;
TreeNode right = TreeNode(preorder[idx]);
node->right = &right;
helper(node->right,dummy+1,end,preorder,inorder);
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode root = TreeNode(preorder[0]);
helper(&root,0,preorder.size()-1,preorder,inorder);
return &root;
}

int main(int argc, const char * argv[]) {
// insert code here..
// build the tree
vector<int> preorder = {2,1,3};
vector<int> inorder = {1, 2, 3};

TreeNode* root = buildTree(preorder,inorder);
return 0;
}


It returned nothing, and when I tried to debug it step by step, I found that the value of left child and right child changed when I got out of the function. I have rewritten the code and use the new TreeNode, and it works.

But I am still confused on the previous version. Is it caused by the way I used to create a TreeNode?

I am not familiar with the C++ pointer, so any hints are appreciated!!

Answer
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    TreeNode root = TreeNode(preorder[0]);
    helper(&root,0,preorder.size()-1,preorder,inorder);
    return &root;
}

Here you are returning address of a locally created object (it will be pointing to some random memory location after the function returns). You need to use new to make the root on the heap. e.g.:

TreeNode* root = new TreeNode(preorder[0]);
//stuff...
return root;

There exist a bit more mistakes in your code...but fixing the pointer above would be the first step to help you debug them out.

Comments