檢查二叉樹是否平衡

我實現了下面的C++代碼片段，以檢查二叉樹是否平衡，即左右子樹的高度相差最多爲1.但是，我不確定是否它很有效，或者以不好的方式反覆檢查子樹。有人可以引導我嗎？檢查二叉樹是否平衡

unordered_map <Node*, int> height; 
    struct Node{ 
     int key; 
     Node* left; 
     Node* right; 
    } 
    bool isBalanced(Node* root){ 
     if (root == nullptr){ 
      height[root] = -1; 
      return true; 
     } 
     if (!isBalanced(root->left)) return false; 
     if (!isBalanced(root->right)) return false; 

     height[root] = max(height[root->left], height[root->right]) + 1; 


     return (abs(height[root->left] - height[root->right]) < 1); 
}

來源

2016-02-23 user25004

您可以'isBalanced'返回'int'，-1不平衡或深度以其他方式。那麼你不需要額外的地圖 – Slava

有很多平衡的樹木，確切地說你的平衡。無論如何，你應該返回高度並比較左右子樹的高度。 –

@DieterLücking混亂。你什麼意思？ – user25004

我會嘗試通過使用僞代碼的想法。

int CheckTreeHeight(Node root) 
{ 
    if(root == null) return 0; // Height of 0. 

    // Check if left is balanaced 
    int leftChildHeight = CheckTreeHeight(root.left); 
    if(leftChildHeight == -1) return -1; // Not Balanced 

    // Check if right is balanaced 
    int rightChildHeight = CheckTreeHeight(root.right); 
    if(rightChildHeight == -1) return -1; // Not Balanced 

    // Check if current node is balanced 
    int heightDifference = leftChildHeight - rightChildHeight; 

    if(Math.abs(heightDifference) > 1) 
    return -1; // not balanaced 
    else 
    return Math.max(leftChildHeight, rightChildHeight) + 1; // Return Height 
} 

bool IsBalanced(Node root) 
{ 
    if(CheckTreeHeight(root) == -1) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
}

此算法執行在O(n)時間複雜度和空間O(H)複雜，其中h是樹的高度。

正如算法的作者提到，這個想法是，我們檢查根的兒童（即left和right）遞歸，直到找到一個平衡，我們返回-1。

使用此技術，如果任何子樹不平衡，我們會立即返回。

有關該實現的更多信息，請參閱下面參考資料中提到的書。

參考
Cracking the Coding Interview 6th Edition

來源

2016-02-23 20:07:41 Rafael

'if（condition）return false;否則返回true;'看起來醜陋，'return！condition;'應該用來代替 – Slava

檢查二叉樹是否平衡

回答

相關問題