algorithm - 最大平衡二叉树的大小

Question

<分区>

Answer 1

一些代码可能会有所帮助。这是 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