Почему значение узла изменилось при выходе из функции?

Question

Я пытаюсь построить двоичное дерево (без дубликата) с его порядком предзаказов и игнорирования в C++.

Кодирование заключается в следующем:

#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; 
} 

Он не вернулся ничего, и когда я пытался отладить его шаг за шагом, я обнаружил, что значение левого ребенка и правом ребенка изменилось, когда я вышел из функция. Я переписал код и использовал новый TreeNode, и он работает.

Но я до сих пор запутался в предыдущей версии. Это вызвано тем, как я использовал для создания TreeNode?

Я не знаком с указателем на C++, поэтому любые подсказки приветствуются!

Answer 1

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

Здесь вы возвращаете адрес локально созданного объекта (он будет указывать на случайную ячейку памяти после возвращения функции). Вы должны использовать new, чтобы сделать корень в куче. например .:

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

Там есть немного больше ошибок в коде ... но фиксируя указатель выше будет первый шаг, чтобы помочь вам отлаживать их.