左神面试算法整理--二叉搜索数最大拓扑结构

算法思想：

建立一个拓扑贡献记录，每个节点左右两侧的值为对于某个节点，此节点拓扑贡献数，如下图：

从图中可以看出，所有的叶子节点对于5来说，他左右两边对5的拓扑贡献均为0，因为他左右两边没有节点。

a图中，在3处来说，对于5来说2符合二叉搜索树的条件，所以他贡献一个，同理4也贡献一个，所以3左右两边各一个。3节点自身也贡献一个，对于5来说左边的节点贡献了3个。右边同理。

图b，12,7大于5,8大于6不满足二叉搜索树条件，所以不能要，也就是不贡献.

那么我们只需要找到某节点，它的左右贡献值最大，那么它就是最大拓扑结构的头结点，左+右+1就是最大值

若在对于以b为头结点的最大子串上加上一个a，让他以a为头结点，若b<a，因为c（c代表b的左子串，不止一个）<b，那么c所代表的左孩子都小于a，满足搜索二叉树条件，所以c对b的贡献可以变成对a的贡献。

对于b的右孩子，若f是大于a的，那么f的贡献就要去除，对于小于a的节点的左孩子也是小于a的，贡献可以直接加上。

JAVA代码：

package chapter_3_binarytreeproblem;


import java.util.HashMap;
import java.util.Map;


public class Problem_08_BiggestBSTTopologyInTree {


public static class Node {
public int value;
public Node left;
public Node right;


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 > 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<Node, Record> map = new HashMap<Node, Record>();
return posOrder(head, map);
}


public static int posOrder(Node h, Map<Node, Record> 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<Node, Record> 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 : n.left, v, m, s);
if (s) {
r.r = r.r - minus;
} else {
r.l = r.l - minus;
}
m.put(n, r);
return minus;
}
}


// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}


public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}


public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}


public static void main(String[] args) {
Node head = new Node(6);
head.left = new Node(1);
head.left.left = new Node(0);
head.left.right = new Node(3);
head.right = new Node(12);
head.right.left = new Node(10);
head.right.left.left = new Node(4);
head.right.left.left.left = new Node(2);
head.right.left.left.right = new Node(5);
head.right.left.right = new Node(14);
head.right.left.right.left = new Node(11);
head.right.left.right.right = new Node(15);
head.right.right = new Node(13);
head.right.right.left = new Node(20);
head.right.right.right = new Node(16);
printTree(head);


System.out.println(bstTopoSize1(head));
System.out.println(bstTopoSize2(head));


}


}