about 35 minutes

import java.util.ArrayList;
import java.util.List;

class Tree {
public int x;
public Tree l;
public Tree r;

public Tree(int x) {
this.x = x;
l = null;
r = null;
}
}

class IntPair {
public int min;
public int max;

public IntPair(int min, int max) {
this.min = min;
this.max = max;
}

public String toString() {
return String.format("(%d, %d)", min, max);
}
}

public class Solution {

List pathPairs = null;

public TreeAmplitude() {
pathPairs = new ArrayList();
}

public int solution(Tree t) {

pathPairs.clear();

amplitude(t, new IntPair(1000000000, -1000000000));

int max = -1000000000;
IntPair p = null;
for (int i = 0; i < pathPairs.size(); i++) {
p = pathPairs.get(i);
System.out.println(p);
max = ((p.max - p.min) > max) ? (p.max - p.min) : max;
}

System.out.println("max = " + max);

return max;

}

private void amplitude(Tree t, IntPair p)
{
if ( t == null ) { return; }

int min = p.min < t.x ? p.min : t.x;
int max = p.max > t.x ? p.max : t.x;
IntPair minMax = new IntPair(min, max);

if (t.l == null && t.r == null) {
pathPairs.add(minMax);
}

if (t.l != null) {
amplitude(t.l, minMax);
}

if (t.r != null) {
amplitude(t.r, minMax);
}

}

public static void main(String[] args) {

Tree t5 = new Tree(5);
Tree t8 = new Tree(8);
Tree t9 = new Tree(9);
Tree t12 = new Tree(12);
Tree t2 = new Tree(2);
Tree t8_ = new Tree(8);
Tree t4 = new Tree(4);
Tree t2_ = new Tree(2);
Tree t5_ = new Tree(5);

t5.l = t8; t5.r = t9;
t8.l = t12; t8.r = t2;
t9.l = t8_; t9.r = t4;
t8_.l = t2_; t4.r = t5_;

Soultion ta = new Solution();
ta.solution(t5);

}

所有跟帖： 

• Good job. I will test code later. -delta101- ♂ (0 bytes) () 09/22/2014 postreply 18:58:31