给定一颗二叉树，已知所有节点的值都不一样， 返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。 拓扑结构是指树上的一个联通块。(非子树概念，是子结构的概念)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; class TreeNode{ TreeNode left; TreeNode right; int val; public TreeNode(int val) { this.val = val; left = null; right = null; } } public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static long mod = (long)Math.pow(2,29); public static void main(String[] args) throws Exception{ String line; String[] strArr; line = reader.readLine(); strArr = line.split(" "); int n = Integer.valueOf(strArr[0]); int rootVal = Integer.valueOf(strArr[1]); Map<Integer, TreeNode> mp = new HashMap<>(n); for (int i = 0; i < n; i++) { line = reader.readLine(); strArr = line.split(" "); int val = Integer.valueOf(strArr[0]); int leftVal = Integer.valueOf(strArr[1]); int rightVal = Integer.valueOf(strArr[2]); if(!mp.containsKey(val)){ mp.put(val, new TreeNode(val)); } if(leftVal != 0){ if(!mp.containsKey(leftVal)){ mp.put(leftVal, new TreeNode(leftVal)); } mp.get(val).left = mp.get(leftVal); } if(rightVal != 0){ if(!mp.containsKey(rightVal)){ mp.put(rightVal, new TreeNode(rightVal)); } mp.get(val).right = mp.get(rightVal); } } TreeNode root = mp.get(rootVal); System.out.println(getMaxSearchTopo(root)); } // 每个节点同样的求法 static int getMaxSearchTopo(TreeNode root){ if(root == null){ return 0; } // 求以 root 为根的最大拓扑结构 int max = 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode cur = queue.poll(); if(isBSTNode(root, cur)){ max++; if(cur.left != null) { queue.add(cur.left); } if(cur.right != null) { queue.add(cur.right); } } } max = Math.max(getMaxSearchTopo(root.left), max); max = Math.max(getMaxSearchTopo(root.right), max); return max; } // 判断 target是否符合BST预期 // 比如 6 和 3 节点比较,依次是(6，3）(2, 3) (3, 3) 符合 // 比如 6 和 20 节点比较,依次是(6，20）(12, 20) (13, 20) (16,20) (null, 20)不符合 static boolean isBSTNode(TreeNode h ,TreeNode target){ if(h == null){ return false; } if(h == target){ return true; } return isBSTNode(target.val < h.val ? h.left : h.right,target); } } /* 6 / \ 2 12 / \ / \ 1 3 10 13 / \ / \ 7 8 20 16 12(10 13) 10 12(13 7 8) 10 12 13(7 8 20 16) 7 10 12 13(8 20 16) （8 在10的左边才行，但是8事实上在10的右边，8要被抛弃） 7 10 12 13(20 16) 7 10 12 13 16 11 6 6 2 12 2 1 3 1 0 0 3 0 0 12 10 13 10 7 8 7 0 0 8 0 0 16 0 0 13 20 16 20 0 0 */
拓扑贡献记录 (左，右可以成为BST的数量)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; class TreeNode{ TreeNode left; TreeNode right; int val; public TreeNode(int val) { this.val = val; left = null; right = null; } } class Record{ int l; // 左边贡献值 int r; // 右边贡献值 public Record(int l, int r) { this.l = l; this.r = r; } } public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static long mod = (long)Math.pow(2,29); public static void main(String[] args) throws Exception{ String line; String[] strArr; line = reader.readLine(); strArr = line.split(" "); int n = Integer.valueOf(strArr[0]); int rootVal = Integer.valueOf(strArr[1]); Map<Integer, TreeNode> mp = new HashMap<>(n); for (int i = 0; i < n; i++) { line = reader.readLine(); strArr = line.split(" "); int val = Integer.valueOf(strArr[0]); int leftVal = Integer.valueOf(strArr[1]); int rightVal = Integer.valueOf(strArr[2]); if(!mp.containsKey(val)){ mp.put(val, new TreeNode(val)); } if(leftVal != 0){ if(!mp.containsKey(leftVal)){ mp.put(leftVal, new TreeNode(leftVal)); } mp.get(val).left = mp.get(leftVal); } if(rightVal != 0){ if(!mp.containsKey(rightVal)){ mp.put(rightVal, new TreeNode(rightVal)); } mp.get(val).right = mp.get(rightVal); } } TreeNode root = mp.get(rootVal); Map<TreeNode, Record> nodeRecordMap = new HashMap<>(); int rs = dfs(root, nodeRecordMap); System.out.print(rs); } // 左右根，后序递归求拓扑贡献记录 static int dfs(TreeNode root, Map<TreeNode, Record> nodeRecordMap){ if(root == null){ return 0; } // 以左，右为根的最大的bfs拓扑结构 int ls = dfs(root.left, nodeRecordMap); int rs = dfs(root.right, nodeRecordMap); // 更新map,方便处理根 modifyMap(root.left, root.val, nodeRecordMap, true); modifyMap(root.right, root.val, nodeRecordMap, false); // 得到左右的情况后，处理根的左右情况 Record lr = nodeRecordMap.get(root.left); Record rr = nodeRecordMap.get(root.right); int lbst = lr == null ? 0 : lr.l + lr.r + 1; int rbst = rr == null ? 0 : rr.l + rr.r + 1; int rootAns = lbst + rbst + 1; nodeRecordMap.put(root, new Record(lbst, rbst)); return Math.max(rootAns, Math.max(ls, rs)); } static int modifyMap(TreeNode n, int v, Map<TreeNode, Record> m, boolean s){ if(n == null || (!m.containsKey(n))){ return 0; } Record r = m.get(n); // node小于起左节点 或者 大于其右边所有，那么是无用的，可以把左或右给删掉了 if((s && n.val > v) || ((!s) && n.val < v)){ m.remove(n); return r.l + r.r + 1; }else { // 否则需要重新设置下左或者右节点的record 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; } } } /* 12(4,?) / \ 10(3,0) 13(0,1) / / \ 4(1,1) 20(0,0) 16(0,0) / \ 2(0,0) 5(0,0) s / a \ b \ c \ d a,b,c都比s小，d比s大，那么 a,b,c左子树能贡献的左值，都能贡献给s */