以遞歸方式查找二叉樹中節點高度的總和

Question

如何遞歸查找二叉樹中節點高度的總和？

例子：

public int totalHeight() { 
    return totalHeight(root); 
} 

private int totalHeight(BinaryNode<AnyType> n) { 

    int totalHeight = 0; 

    if (n.left == null && n.right == null) 
     return totalHeight; 
    if (n.left != null && n.right != null) 
     return totalHeight + 1 
       + Math.max(totalHeight(n.left), totalHeight(n.right)); 
    if (n.left != null) 
     return totalHeight + 1 + Math.max(totalHeight(n.left), -1); 
    if (n.right != null) 
     return totalHeight + 1 + Math.max(-1, totalHeight(n.right)); 

    return totalHeight; 
} 

我已經試過這一點，但只得到了樹的所有節點的高度的高度，而不是總和。

我感覺很難跟蹤計數器的遞歸，似乎totalHeight設置爲0，每次遞歸調用。不是很好。

Answer 1

private int maxHeight(BinaryNode<AnyType> n) { 
    if (n ! = null) return 0; 
    int leftheight = maxHeight(n.left); 
    int rightheight = maxHeight(n.right); 
    return (leftheight > rightheight) ? leftheight + 1 : rightheight + 1; 
} 

到目前爲止，您已經知道了4例數高度

本質是繼續當左子或右子存在去左或右節點。 如果存在，返回1.

計數函數進入最後一個語句。這是爲了獲得最大的高度。

主要過程是在方法正常工作時熟悉遞歸和編程堆棧。

Answer 2

重新找到每個節點的高度並不斷添加到靜態變量中。或者，您可以記住高度並存儲在每個節點中，然後執行另一次遞歸來添加它們。

遞歸應返回節點n的高度，而不是子樹中每個節點的總高度。

Answer 3

鑑於你一個節點的高度的實施，讓我們簡單地把它height(BinaryNode<?>)，您可以：

如果你有機會到所有節點集合中：

int sumHeight(List<BinaryNode<?>> nodes) { 
    int sum = 0; 
    for (BinaryNode<?> node: nodes) { 
     sum += height(node); 
    } 
    return sum; 
} 

如果你只有訪問節點的樹狀結構：

int sumHeight(BinaryNode<?> node) { 
    if (node == null) return 0; 
    return height(node) + sumHeight(node.left) + sumHeight(node.right); 
} 

，看看是否有正在算法中的，可以在一個遞歸（也許有些backtra做計算這將是有趣cking算法？）。

Answer 4

一個簡單的版本將做一個雙通過程，首先記錄每個節點的高度，然後迭代節點進行總結。這種方法可以遞歸，但是通過在計算高度時加起來就可以輕鬆完成。

public static int totalHeightSum = 0; 

private int calculateHeightAndAdd (Node n) 
{ 
    if (n == null) 
     return 0; 

    int leftHeight = calculateHeightAndAdd (n.left); 
    int rightHeight= calculateHeightAndAdd (n.right); 

    int myHeight = 1 + Math.max (leftHeight, rightHeight); 

    totalHeightSum += myHeight; 

    return myHeight; 
} 

Answer 5

好的。我已經提出了一個解決方案。

a）如n == null返回0

b）如n.left == null && n.right == null返回0

C）的總高度爲total height of left + total height of right + the height of it self

• 的本身的高度是：

1）如果左側的左減去總高度大，則總高度離開的左

2）如果右側是右的右

public int totalHeight() { 
    return totalHeight(root); 
} 

private int totalHeight(BinaryNode<AnyType> n) { 
    if (n == null) 
     return 0; 
    else if (n.left == null && n.right == null) 
     return 0; 
    else 
     return totalHeight(n.left) 
       + totalHeight(n.right) 
       + (totalHeight(n.left) > totalHeight(n.right) ? totalHeight(n.left) 
         - (n.left == null ? 0 : totalHeight(n.left.left)) 
         : totalHeight(n.right) 
           - (n.right == null ? 0 
             : totalHeight(n.right.right))) + 1; 
} 

Answer 6

右減去總高度大，則總高度我假設你在插入過程中沒有更新高度。

解決方案： 我會按順序遍歷樹。所以我首先聲明root.height = 0。

然後說

BinaryNode right; 
BinaryNode left; 
BinaryNode parent; 
static int level; 
int height; 


if(left!=null) 
{ 
    left.height=left.parent.height+1; 
    level=level+left.height; 
    left.yourMethod(); 
} 

if(right!=null) 
{ 
    right.height= right.parent.height+1; 
    level=level+right.height; 
    right.yourMethod(); 
} 

所以，你現在有一個存儲所有的高度水平。

另一種方法可以是使用隊列的廣度優先搜索遍歷，但答案是相同的。 希望這有助於。

Answer 7

空隙addHeights（分類*根，INT深度，整數&總和） { 如果（根） { addHeights（根 - >左，深度+ 1，總和）;
addHeights（root-> right，depth + 1，sum）; sum + = depth; sum + = depth; }}

Answer 8

public int sum(){ 
    return sum(root); 
} 
private int sum(BinaryNode <?> n){ 
    if(n == null) 
     return 0; 
    else 
     return n.data + sum(n.left) + sum(n.right); 

} 

我需要更多的數據來評估你的代碼，雖然我假設你叫節點「數據」中的數據。

因此，如果節點爲空，則意味着您已到達樹的末尾並返回0.否則，它將採用數據並遍歷左側然後到右側。隨着每次遞歸，它們將被添加，直到它們沒有更多節點被添加。