C++结构在递归返回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

new操作符将动态分配将存储在堆中的内存。第二个版本不能工作，只需创建变量并将其存储在堆栈中。函数调用完成后，所有信息都将从堆栈中弹出，存储在这些内存位置的任何信息都将不再被视为有效。也就是说，return &root在该函数完成后返回无效的地址。

Answer 2

您的不同之处在于您已经创建了一个悬吊指针。简而言之，您不应该返回局部变量的地址(通过引用)，因为局部变量在超出作用域时会被取消分配。相反，您应该返回root的副本(按值)。因此，不需要&，但是如果树数据不是原始类型的(不是int、double、...etc)，请确保有一个复制构造函数。