程序员代码面试指南 3.13：判断二叉树是否为平衡二叉树

1、思路

• 用一个 getDeep 函数计算当前子树的深度；

• 每次递归都要判断 root 的左右子树是否平衡，并判断以 root 为根节点的子树是否平衡。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode *root, int &n)     //建树
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

int getDeep(TreeNode *root)                     //递归计算当前子树的深度
{
    if (root == nullptr) return 0;

    return max(getDeep(root->left), getDeep(root->right)) + 1;
}

bool isBalanced(TreeNode *root)
{
    if (root == nullptr) return true;

    //递归判断 root 的左右子树是否平衡，并判断以 root 为根节点的子树是否平衡
    return isBalanced(root->left) && isBalanced(root->right) && 
            abs(getDeep(root->left) - getDeep(root->right) <= 1);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root, n);

    if (isBalanced(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}