balanced（）二叉樹

我需要編寫一個方法來確定二叉樹是否平衡。所以首先我必須確定樹的每一邊的高度。但是我很難理解我將如何計算子樹的最大長度，而不計算子樹中的所有節點。這個問題很難問我，所以你們可以理解。balanced（）二叉樹

// primary method 
public int Height() 
{ 
    int h = height(root); 
} 

// recursive method 
private int height(Node x) 
{ 
    if(x == null) return 0; 
    count++;     
    height(x.left); 
    height(x.right); 
    return count;   
}

這是我的代碼，用於計算樹的最大高度。但我不知道如何確定只是左側或右側的高度，和這種方法似乎計算在樹本身的節點數量。

來源

2011-04-30 Ruben Van St Aden

聞起來像功課！ – CoolBeans 2011-04-30 17:37:42

是的，我知道。但這就是爲什麼我沒有要求孔平衡樹，只是高度和概念如何開始balnced樹。爲什麼我的代碼出來如此studip？ – 2011-04-30 17:39:34

愚蠢，對不起... – 2011-04-30 17:40:06

由於return;聲明 - 這個方法不會編譯，所以你需要返回一個int。因此，if(x == null)，你應該返回什麼？空樹的高度是多少？

一旦你明白了，想象你的根只有一個左子樹（root.right == null），並且你知道左子樹的高度。整棵樹的高度應該是多少？

如果它只有一個正確的子樹會怎麼樣？

現在，如果它有兩個呢？

請注意，您不需要全局計數變量。

來源

2011-04-30 17:41:39

好初學者錯誤與第一個返回值。如果在那裏更改我的代碼。 – 2011-04-30 17:52:48

高度爲1 + max（left.height（），right.height（））。

你應該返回一個值，而不是設置變量（計數，你的情況），否則你會發瘋。

來源

2011-04-30 17:42:05 akappa

但我不明白的是，left.height（）和right.height（）只會返回0.如果不計算一個值，他們如何返回一個值？ – 2011-04-30 17:54:18

但我不明白的是，left.height（）和right.height（）將返回0.如果他們不算一個值，他們如何返回一個值？ – 2011-04-30 17:54:19

cuase我說當到達葉子時返回0 – 2011-04-30 17:54:51

節點的高度比其最高子節點的高度大1（提示：使用Math.max）。

來源

2011-04-30 17:42:23 sjr

添加提示我還會指出，你真的想使用遞歸。

來源

2011-04-30 20:53:26

balanced（）二叉樹

回答

相關問題