最大的平衡二進制子樹的大小

我想創建一個分而治之的算法，當在二叉樹的根上運行時，返回樹中或其他樹中包含的最大平衡二進制子樹的大小單詞，可能葉子都在同一深度的最大子樹的大小。最大的平衡二進制子樹的大小

2017-07-24 John Lee

只有一個遍歷：寫一個遞歸函數，該函數返回兩個數字的節點：'了'：見過的最大平衡子樹（這是輸出）和'b'：如果節點有平衡的孩子，則返回深度。如果沒有平衡的孩子，則返回0.您可以通過遞歸調用來計算節點的'b'。如果返回的深度匹配，則可以返回深度+ 1代替'b'，否則爲零。你需要用'b'更新'a'。就這樣。 – geza

對不起，我沒有關注。你能進一步闡述一下嗎？爲什麼你爲一個節點返回兩個數字？如果返回的深度匹配，爲什麼你爲b返回深度+1？你用b更新什麼？ –

需要返回2個數字，因爲一個（b）存儲當前深度，如果節點不平衡，則當前深度可以爲零。所以需要a來存儲當前看到的最大值，這不能減小。通過更新，我的意思是一個簡單的if：if（a geza

某些代碼可能會有所幫助。這是Java，但它非常通用。

static class Node 
{ 
    String val; 
    Node left, right; 
} 

static class MaxNode 
{ 
    Node node; 
    int depth; 
} 

static int depth(Node node) 
{ 
    if(node.left == null && node.right == null) 
    { 
     return 0; 
    } 
    else 
    { 
     return 1; 
    } 
} 

static int deepestSubtree(Node root, MaxNode maxNode) 
{ 
    if(root == null) return 0; 

    int depth = depth(root); 

    int leftDepth = deepestSubtree(root.left, maxNode); 
    int rightDepth = deepestSubtree(root.right, maxNode); 

    if(leftDepth == rightDepth) 
    { 
     depth += leftDepth; 
    } 

    if(depth > maxNode.depth) 
    { 
     maxNode.node = root; 
     maxNode.depth = depth; 
    } 

    return depth; 
} 

public static void main(String[] args) 
{ 
    Node root = buildTree(); 

    MaxNode maxNode = new MaxNode(); 
    deepestSubtree(root, maxNode); 
    if(maxNode.node == null) 
    { 
     System.out.println("No Balanced Tree"); 
    } 
    else 
    { 
     int size = (int)Math.pow(2, maxNode.depth+1)-1; 
     System.out.format("Node: %s, Depth: %d, Size: %d\n", maxNode.node.val, maxNode.depth, size); 
    } 
}

對於示例樹的輸出是：需要

Node: D, Depth: 2, Size: 7

來源

2017-07-24 17:52:11 SirRaffleBuffle

最大的平衡二進制子樹的大小

回答

相關問題