Ich versuche einen Divide-and-Conquer-Algorithmus zu erstellen, der, wenn er auf der Wurzel eines Binärbaums ausgeführt wird, die Größe des größten ausgeglichenen binären Teilbaums im Baum oder in anderem zurückgibt Wörter, die Größe der größten Teilbaum möglich, wo die Blätter alle in der gleichen Tiefe sind.Größe des größten ausgeglichenen binären Teilbaums
Einige Codes könnten helfen. Das ist Java, aber es ist ziemlich generisch.
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);
}
}
Für Ihr Beispiel Baum der Ausgang ist:
Node: D, Depth: 2, Size: 7
Nur ein Traversal benötigt wird: eine rekursive Funktion schreiben, die für einen Knoten zwei Zahlen zurück: 'a': die größte ausgewogene Unterbaum gesehen (dies ist die Ausgabe) und "b": Wenn der Knoten ausgeglichene Kinder hat, dann gibt er die Tiefe zurück. Wenn keine ausgeglichenen untergeordneten Elemente vorhanden sind, geben Sie 0 zurück. Sie können "b" für einen Knoten berechnen, indem Sie rekursiv aufrufen. Wenn die zurückgegebenen Tiefen übereinstimmen, können Sie Tiefe + 1 für "b" zurückgeben, andernfalls null. Und Sie müssen 'a' mit' b' aktualisieren. Das ist alles. – geza
Es tut mir leid, ich folge nicht. Können Sie weiter ausführen? Warum gibst du zwei Zahlen für einen Knoten zurück? Warum geben Sie Tiefe + 1 für b zurück, wenn die zurückgegebenen Tiefen übereinstimmen? Und womit aktualisierst du a mit b? –
2 Zahlen werden benötigt, weil man (b) die aktuelle Tiefe speichert, die Null sein kann, wenn der Knoten unausgewogen ist. So wird benötigt, um das aktuelle Maximum zu speichern, das nicht verringert werden kann. Mit update meine ich ein einfaches wenn: if (a
geza