二叉树结构平衡，使用递归时EXC_BAD_ACCESS

Question

我工作的问题，以检查如果二进制结构树是平衡或不，当我运行代码，我得到EXC_BAD_ACCESS，我不确定如何修复问题，是什么导致它打破。

假设代码在某个时刻命中 NULL 并返回 （true，-1），并深入到左侧子树。然后返回并转到右侧子树。我们可以检查左和右的子树是否由不同的平衡，如果它是

谢谢

#include <iostream>
using namespace std;

struct TreeNode {
    TreeNode * left;
    TreeNode * right;
};


class balanceStatusAndHeight{
public:
    bool isBalanced;
    int height;
    balanceStatusAndHeight(bool isBalanced, int height);
};


balanceStatusAndHeight::balanceStatusAndHeight(bool isBalanced, int height) {
    this->isBalanced = isBalanced;    
    this->height = height;
}




balanceStatusAndHeight checkBalance(TreeNode * root) {    

    if (root == NULL ) {
        return balanceStatusAndHeight(true, -1);
    }

    balanceStatusAndHeight leftResult = checkBalance(root->left);
    if ( !leftResult.isBalanced  ) {
        return leftResult;
    }

    balanceStatusAndHeight rightResult = checkBalance(root->right);
    if ( !rightResult.isBalanced) {
        return rightResult;
    }


    bool subTreesAreBalanced = abs(leftResult.height - rightResult.height) <= 1;
    int height = max(leftResult.height, rightResult.height) + 1;

    return balanceStatusAndHeight(subTreesAreBalanced, height);

};




int main(int argc, const char * argv[]) {

    TreeNode *a = new TreeNode;
    a->left = new TreeNode;
    a->left->left = new TreeNode;

    balanceStatusAndHeight c = checkBalance(a);


    cout << c.isBalanced << endl;



    return 0;
}

Answer 1

在< code >检查余额中

if (root == NULL ) 

要求树分支以< code>NULL终止。不幸的是，代码中没有任何东西可以确保树是以< code>NULL终止的，所以当测试遇到未初始化的< code>left或< code>right指针，然后程序试图访问未初始化指针处的无效< code>TreeNode时，测试就会失败。

有了现代编译器

struct TreeNode {
    TreeNode * left = NULL; // but prefer nullptr to NULL as it has better type safety
    TreeNode * right = NULL;
};

解决了这个问题。由于正在使用NULL而不是nullptr，编译器可能很旧或故意设置为较旧的C标准修订版，因此需要一个构造函数。

struct TreeNode {
    TreeNode * left;
    TreeNode * right;

    TreeNode():left(NULL), right(NULL)
    {

    }
};

一个更聪明的构造器或者对聚合初始化的巧妙使用可以让你的生活更轻松。

此更改后程序是否正常工作？不知道。没有测试。但是，它不会崩溃。