Что если для каждого узла n ваша цель состояла в том, чтобы вычислить эти два числа:
- f (
n): длина самого длинного пути в дереве с корнем в n
- h (
n): высота дерева с корнем в n.
Для каждого конечного узла (узлы, имеющие null левый и правый узлы), очевидно, что f и h оба равны 0.
Теперь h каждого узла n:
- 0, если
n.left и n.right оба null
- 1 + ч (
n.left), если только n.left не является null
- 1 + h (
n.right), если только n.right не является null
- 1 + макс (ч (
n.left), ч (n.right)), если оба n.left и n.right не являются null
А f (n) равно:
- 0, если
n.left и n.right оба null
- max (f (
n.left), h (n)), если только n.left не является null
- ?? если только
n.right не является null
- ?? если
n.left и n.right не являются null
(Вам нужно выяснить, что заменяет два заполнителя "??". Есть варианты, которые заставляют эту стратегию работать. Я лично проверил ее.)
Тогда longestPath(Node n) - это просто f (n):
public class SO3124566
{
static class Node
{
Node left, right;
public Node()
{
this(null, null);
}
public Node(Node left, Node right)
{
this.left = left;
this.right = right;
}
}
static int h(Node n)
{
// ...
}
static int f(Node n)
{
// ...
}
public static int longestPath(Node n)
{
return f(n);
}
public static void main(String[] args)
{
{ // @phimuemue's example
Node n6 = new Node(),
n9 = new Node(),
a = new Node(),
n7 = new Node(n9, a),
n4 = new Node(n6, n7),
b = new Node(),
n8 = new Node(null, b),
n5 = new Node(null, n8),
n2 = new Node(n4, n5),
n3 = new Node(),
n1 = new Node(n2, n3);
assert(longestPath(n1) == 6);
}{ // @Daniel Trebbien's example: http://pastebin.org/360444
Node k = new Node(),
j = new Node(k, null),
g = new Node(),
h = new Node(),
f = new Node(g, h),
e = new Node(f, null),
d = new Node(e, null),
c = new Node(d, null),
i = new Node(),
b = new Node(c, i),
a = new Node(j, b);
assert(longestPath(a) == 8);
}
assert(false); // just to make sure that assertions are enabled.
// An `AssertionError` is expected on the previous line only.
}
}
Вы должны быть в состоянии написать рекурсивные реализации f и h, чтобы этот код работал; Однако это решение ужасно неэффективно. Его цель - просто понять расчет.
Чтобы повысить эффективность, вы можете использовать памятка или преобразовать это в нерекурсивный расчет, который использует стек (ы).