이 진 트 리 에서 이 진 트 리 검색 조건 에 맞 는 최대 토폴로지 구 조 를 찾 습 니 다.

이 진 트 리 에서 이 진 트 리 검색 조건 에 맞 는 최대 토폴로지 구 조 를 찾 습 니 다.
이 진 트 리 의 머리 노드 헤드 를 지정 합 니 다. 모든 노드 의 값 이 다르다 는 것 을 알 고 있 습 니 다. 그 중에서 가장 큰 것 을 되 돌려 주 고 이 진 트 리 를 검색 하 는 데 부합 합 니 다.
조건 의 토폴로지 구조의 노드 수.이곳 의 토폴로지 구 조 는 이 진 트 리 에서 특정한 노드 를 임의로 선택 할 수 있다 는 것 을 말한다. 이 노드 가 연결 되 어 있 으 면 이 진 트 리 의 토폴로지 구조 라 고 부른다.

public static class Node{
	public int value;
	public Node right;
	public Node left;
	public Node(int data){
		this.value = data;
	}
}

public static int bstTopoSize1(Node head){
	if(head == null){
		return 0;
	}
	int max = maxTopo(head, head);
	max = Math.max(bstTopoSize1(head.left), max);
	max = Math.max(bstTopoSize1(head.right), max);
	return max;
}

public static int maxTopo(Node h, Node n){
	if(h != null && n != null && isBSTNode(h,n,n.value)){
		return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
	}
	return 0;
}

public static boolean isBSTNode(Node h, Node n, int value){
	if(h == null){
		return false;
	}
	if(h == n){
		return true;
	}
	return isBSTNode(h.value > h.left : h.right, n, value);
}

public static class Record{
	public int l;
	public int r;
	public Record(int left, int right){
		this.l = left;
		this.r = right;
	}
}

public static int bstTopoSize2(Node head){
	Map map = new HashMap();
	return posOrder(head, map);
}

public static int posOrder(Node h, Map map){
	if(h == null){
		return 0;
	}
	int ls = posOrder(h.left, map);
	int rs = posOrder(h.right, map);
	modifyMap(h.left, h.value, map, true);
	modifyMap(h.right, h.value, map, false);
	Record lr = map.get(h.left);
	Record rr = map.get(h.right);
	int lbst = lr = null ? 0 : lr.l + lr.r + 1;
	int rbst = rr = null ? 0 : rr.l + rr.r + 1;
	map.put(h, new Record(lbst, rbst));
	return Math.max(lbst + rbst + 1, Math.max(ls, rs));
}

public static int modifyMap(Node n, int v, Map m, boolean s){
	if(n == null || (!m.containsKey(n))){
		return 0;
	}
	Record r = m.get(n);
	if((s && n.value > v) || ((!s) && n.value < v)){
		m.remove(n);
		return r.l + r.r + 1;
	}else{
		int minus = modifyMap(s ? n.right, v, m, s);
		if(s){
			r.r = r.r - minus;
		}else{
			r.l = r.l - minus;
		}
		m.put(n, r);
		return minus;
	}
}