Pourquoi la valeur de noeud a-t-elle changé lors de la sortie de la fonction?

Question

J'essaie de construire un arbre binaire (pas de doublon) avec sa séquence de précommande et d'ignorant en C++.

Le codage est comme suivant:

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

Il est revenu rien, et quand j'ai essayé de déboguer étape par étape, je trouve que la valeur de l'enfant enfant gauche et à droite a changé quand je suis sorti de la fonction. J'ai réécrit le code et utilise le nouveau TreeNode, et cela fonctionne.

Mais je suis toujours confus sur la version précédente. Est-ce causé par la façon dont j'ai créé un TreeNode?

Je ne suis pas familier avec le pointeur C++, donc toutes les astuces sont appréciées !!

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

Ici, vous renvoyez l'adresse d'un objet créé localement (il pointera vers un emplacement de mémoire aléatoire après le retour de la fonction). Vous devez utiliser new pour faire la racine sur le tas. .: par exemple

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

Il existe un peu plus d'erreurs dans votre code ... mais fixer le pointeur ci-dessus serait la première étape pour vous aider à déboguer dehors.