Размер наибольшего сбалансированного двоичного поддерева

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