找到二叉树中符合搜索二叉树条件的最大拓扑结构

本文主要是介绍找到二叉树中符合搜索二叉树条件的最大拓扑结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

import java.util.*;
//找到二叉树中符合搜索二叉树条件的最大拓扑结构public class MaxSearchTreeTuo{//二叉树节点的定义public static class Node{public int value;public Node left;public Node right;public Node(int data){this.value=data;}}//获得最大拓扑结构的大小public static int bstTopSize(Node head){if(head==null){return 0;}int max=MaxTopo(head,head);max=Math.max(bstTopSize(head.left),max);max=Math.max(bstTopSize(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;}}public static void main(String []args){//System.out.println("Hello");Node node=new Node(12);node.left=new Node(10);node.right=new Node(13);node.left.left=new Node(4);node.left.right=new Node(14);node.right.left=new Node(20);node.right.right=new Node(16);node.left.left.left=new Node(2);node.left.left.right=new Node(5);node.left.right.left=new Node(11);node.left.right.right=new Node(15);System.out.println(bstTopSize(node));System.out.println(bstTopoSize2(node));}
}