BST高度算法

Question

class node 
{ 
    private float data; 
    private node left; 
    private node right; 

    public int TreeHeight(int depth) 
    {  
     root vL = left;//access to left data 
     root vR = right; 

     return depthOfTheTree; 
    } 
} 

樹看起來像這樣：http://imgur.com/EBS30rl

你好，我是做對返回樹的高度的一種方法算法。 該方法只能訪問左右節點。可變深度作爲參數已經爲方法本身賦值1（計算樹的根）。 我已經嘗試過遞歸調用方法，但結果並不接近預期。 我之前的代碼與下面的代碼類似。

public int TreeHeight(int depth) 
{ 
    if (left != null && right == null) 
     return left.TreeHeight(depth); 
    else if (left == null && right != null) 
     return right.TreeHeight(depth); 
    else 
     return left.TreeHeight(depth) + right.TreeHeight(depth); 
} 

Answer 1

通過definition：

節點的高度是節點和葉之間的最長路徑上的邊的數量。

對於BST它可以遞歸表示爲（僞碼）：

height(node) = 
{ 
    0, when node == null 
    1 + max(height(node.left), height(node.right)), when node != null 
} 

因此遞歸方法不需要depth參數，並且可以是這樣的：

public int TreeHeight() 
{ 
    return 1 + Math.Max(
     left != null ? left.TreeHeight() : 0, 
     right != null ? right.TreeHeight() : 0 
    ); 
} 

和與C＃6 null conditional operator，實施可能很簡單，因爲：

return 1 + Math.Max(left?.TreeHeight() ?? 0, right?.TreeHeight() ?? 0);