最大的平衡二进制子树的大小

我想创建一个分而治之的算法，当在二叉树的根上运行时，返回树中或其他树中包含的最大平衡二进制子树的大小单词，可能叶子都在同一深度的最大子树的大小。最大的平衡二进制子树的大小

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

最大的平衡二进制子树的大小

回答

相关问题