剑指offer之判断二叉树是不是平衡二叉树

1 问题

判断二叉树是不是平衡二叉树

平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

 
2 代码实现

    int getTreeHeigh(Node *haed)
    {
        if (head == NULLL)
        {
            return 0;
        }
        int left = getTreeHeigh(head->left);
        int right = getTreeHeigh(head->right);
        retur left > right ? (left + 1) : (right + 1);
    }
     
    int isBalancedTree(Node *head)
    {
        if (head == NULL)
        {
            return NULL;
        }
        int left, right;
        left = isBalancedTree(head->left);
        right = isBalancedTree(head->right);
        int result = left - right;
        if (result > 1 || result < -1)
            return false;
        return isBalancedTree(head->left) && isBalancedTree(head-right);
    }

 


 




 


作者:chen.yu
深信服三年半工作经验,目前就职游戏厂商,希望能和大家交流和学习,
微信公众号:编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)