強烈平衡樹 - 改進

我有以下的結構來表示二叉樹：強烈平衡樹 - 改進

typedef struct node *pnode; 
typedef struct node { 
    int val; 
    pnode left; 
    pnode right; 
} snode;

重樹是從樹中的所有節點的val參數的總和。我們說樹是強烈平衡當它是空的或左權重等於右子樹的權重和每個子樹（左和右）強烈平衡。我必須編寫函數來告訴樹是否強烈平衡。

的代碼，我寫道：

int getWeight(pnode tree) 
{ 
    if(! tree) 
     return 0; 
    return getWeight(tree->left) + getWeight(tree->right) 
      + tree->val; 
} 

bool isStronglyBalanced(pnode tree) 
{ 
    if(! tree) 
     return true; 

    int wL, wR; 
    wL = getWeight(tree->left); 
    wR = getWeight(tree->right); 

    if(wL != wR) 
     return false; 
    return (isStronglyBalanced(tree->left) && isStronglyBalanced(tree->right)); 
}

上面的函數，它的工作不錯，但我注意到它的訪問不止一次樹的節點。是否可以改進（也許通過使用動態編程）來訪問樹的每個節點一次？

來源

2016-02-09 threaz

如果getweight也告訴你子樹是否強烈平衡，可以將代碼簡化爲單次掃描。

有幾種方法可以從函數調用中返回兩條信息。如果有一些你知道的返回值永遠不會是一個子樹的權重（可能是一個負數），那麼你可以用它作爲子樹不是很強平衡的信號。或者您可以簡單地返回兩個值：一個bool和一個int。（在C中，你可以爲其中一個使用「out」參數）。或者你可以用兩個值定義一個複合對象，這在C中是struct { bool balanced; int weight; }。

但是你這樣做，邏輯是一樣的。在下面的僞代碼，我只是假設，你可以在一些語言中，你可以返回值對（C++，例如，但儘管任何休閒相似，但它仍然是僞代碼）：

pair<bool, int> get_weight(tree) { 
    if (!tree) return {true, 0}; 
    balanced, weight_left = get_weight(tree->left); 
    if (!balanced) return {false, 0};  /* Returned weight doesn't matter */ 
    balanced, weight_right = get_weight(tree->right); 
    return {balanced && weight_left == weight_right, 
      2 * weight_right + tree->val}; /* weight_left == weight_right */ 
}

來源

2016-02-09 20:50:52 rici

這是一個很好的建議，但是不應該將返回值設爲'{balanced && weight_left == weight_right，weight_right + weight_left + tree-> val}'？ –

@DougCurrie：的確如此。謝謝。修正了，注意到weight_left == weight_right。 – rici

強烈平衡樹 - 改進

回答

相關問題