劍指offer之判斷二叉樹是不是平衡二叉樹

1 問(wèn)題

判斷二叉樹是不是平衡二叉樹

平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹

 
2 代碼實(shí)現(xiàn)

    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
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)