Binary Tree Structure Balanced , EXC_BAD_ACCESS 使用递归时

Question

我正在研究检查二进制结构树是否平衡的问题，当我运行代码时，我得到 EXC_BAD_ACCESS 我不确定如何解决问题以及是什么导致它破裂。

代码假设在某个时候命中 NULL 和 return (true,-1) 并深入左子树。然后 return 并转到右子树。如果 <= 1，我们可以检查左右子树是否平衡，并通过每个节点的 max(left,right) +1 获取其高度。 if <= 1 表示不平衡 returns (false , height) 并且它冒泡到递归。

谢谢

#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

在checkBalance

if (root == NULL )

预计树枝将 NULL 终止。不幸的是，代码中没有任何东西可以确保树 NULL 终止，因此当它遇到未初始化的 left 或 right 指针时，此测试失败，然后程序尝试访问无效的 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)
    {

    }
};

更聪明的构造函数或巧妙地使用 aggregate initialization 可以让您的生活更轻松。

此更改后程序是否有效？不知道。没有为此进行测试。不过它退出时没有崩溃。

Binary Tree Structure Balanced , EXC_BAD_ACCESS 使用递归时

Binary Tree Structure Balanced , EXC_BAD_ACCESS when using recursion

c++

algorithm

binary-tree