C ++ Struct в рекурсии return nullptr？

Question

Я решал leetcode 106 .Я знаю, как использовать рекурсию в этой задаче.Но я запутался в инициализации структуры.Переданная версия выглядит следующим образом:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = inorder.size();
        if (inorder.empty() && postorder.empty())
            return nullptr;
        return buildTree(inorder, 0, len - 1, postorder, 0, len - 1);
    }

    int getIndex (vector<int> order, int key)
    {
        int i = 0;
        for(int n: order)
        {
            if (n == key)
                break;
            i++;
        }
        return i;
    }

    TreeNode* buildTree(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe)
    {
        if (is > ie || ps > pe)
            return nullptr;
        TreeNode* root = new TreeNode(postorder[pe]);
        int index = getIndex(inorder, postorder[pe]);
        //cout<< index <<" "<<postorder[pe]<< endl;
        root->left = buildTree(inorder, is, index - 1, postorder, ps, ps + index - is - 1);
        root->right = buildTree(inorder, index + 1, ie, postorder, pe - ie + index,pe - 1);
        return root;
    }
};

Затем я изменил другой способ инициализации структуры следующим образом:

TreeNode* buildTree(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe)
{
    if (is > ie || ps > pe)
        return nullptr;
    struct TreeNode root(postorder[pe]);
    int index = getIndex(inorder, postorder[pe]);
    //cout<< index <<" "<<postorder[pe]<< endl;
    root.left = buildTree(inorder, is, index - 1, postorder, ps, ps + index - is - 1);
    root.right = buildTree(inorder, index + 1, ie, postorder, pe - ie + index,pe - 1);
    //cout<< root.val << " " << root.right << " " << root.left <<endl;
    return &root;
}

эта версия всегда возвращает nullptr.Так что же не так и в чем разница между этими двумя способами?

Answer 1

Разница в том, что вы создали Dangling Pointer .Короче говоря, вы не должны возвращать адрес (по ссылке) локальной переменной, потому что локальные переменные освобождаются, когда они находятся вне области видимости.Вместо этого вы должны вернуть копию root (по значению).Следовательно, & не требуется, но убедитесь, что у вас есть конструктор копирования, если данные дерева не относятся к примитивному типу (не int, double, ... и т. Д.)

Answer 2

Оператор new будет динамически выделять память, которая будет храниться в куче .Вторая версия, которая не работает, просто создает переменную и сохраняет ее в стеке.После завершения этого вызова функции вся информация будет выгружена из стека, и все, что было сохранено в этих ячейках памяти, больше не будет считаться действительным.то есть поговорка return &root возвращает неверный адрес после выполнения этой функции.