给定一颗二叉树,已知所有节点的值都不一样, 返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。
拓扑结构是指树上的一个联通块。
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
ps:节点的编号就是节点的值。
输出一个整数表示满足条件的最大拓扑结构的大小。
3 2 2 1 3 1 0 0 3 0 0
3
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } // 拓扑贡献记录 class Record { public int left; // 左孩子贡献的BST节点数 public int right; // 右孩子贡献的BST节点数 public Record(int left, int right) { this.left = left; this.right = right; } } public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); HashMap<Integer, TreeNode> map = new HashMap<>(); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]); // 构建二叉树 TreeNode root = new TreeNode(rootVal); map.put(rootVal, root); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int nodeVal = Integer.parseInt(params[0]); int leftVal = Integer.parseInt(params[1]); int rightVal = Integer.parseInt(params[2]); TreeNode node = map.get(nodeVal); if(leftVal != 0) { node.left = new TreeNode(leftVal); map.put(leftVal, node.left); } if(rightVal != 0) { node.right = new TreeNode(rightVal); map.put(rightVal, node.right); } } // 求解 System.out.println(maxBstTopoSize(root)); } private static int maxBstTopoSize(TreeNode head) { HashMap<TreeNode, Record> map = new HashMap<>(); // 用于存储各个节点的拓扑贡献记录 return postOrder(head, map); } private static int postOrder(TreeNode head, HashMap<TreeNode, Record> map) { if(head == null) return 0; int leftSize = postOrder(head.left, map); int rightSize = postOrder(head.right, map); // 检查头结点能够囊括左右孩子多少节点,并修改孩子节点的贡献记录 modifyMap(head.left, head.val, map, true); modifyMap(head.right, head.val, map, false); // 获得左右孩子的贡献记录 Record leftRecord = map.get(head.left); Record rightRecord = map.get(head.right); // 计算左右孩子贡献的BST节点数 int leftBST = leftRecord == null? 0: leftRecord.left + leftRecord.right + 1; int rightBST = rightRecord == null? 0: rightRecord.left + rightRecord.right + 1; map.put(head, new Record(leftBST, rightBST)); return Math.max(leftBST + rightBST + 1, Math.max(leftSize, rightSize)); } public static int modifyMap(TreeNode node, int rootVal, HashMap<TreeNode, Record> map, boolean isLeftTree) { if(node == null || (!map.containsKey(node))) return 0; Record record = map.get(node); // 获得当前节点node的拓扑贡献记录 if((isLeftTree && node.val > rootVal) || ((!isLeftTree) && node.val < rootVal)){ // 如果左树的右边界节点node比根的值大,或者右树的左边界节点node比根的值小,就移除node的贡献 map.remove(node); return record.left + record.right + 1; // 要把node节点及其孩子节点的贡献返回去让上层节点删除掉 }else{ // 是左树就递归检查右边界,是右树就递归检查左边界 int minus = modifyMap(isLeftTree? node.right: node.left, rootVal, map, isLeftTree); // 沿途修改边界节点node的贡献记录 if(isLeftTree){ record.right = record.right - minus; }else{ record.left = record.left - minus; } map.put(node, record); return minus; } } }
import java.util.*; class Node { public int val; public Node left; public Node right; public Node (int val) { this.val = val; } } /* 记录节点贡献值:对每一个节点生成(a, b)其中a代表当前节点左子树在二叉树的拓扑结构中可以给你贡献几个节点, 同理b表示。。。。。右子树。。。。。 采取后序遍历的形式从下往上设置贡献值,若换头节点了,先查左右子节点是否符合二叉树,后查左子节点的右子树和右子节点的左子树 */ class Record { public int l; public int r; public Record (int l, int r) { this.l = l; this.r = r; } } public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Node head = constructTree(sc, n); int result = returnSize(head); System.out.println(result); } public static Node constructTree (Scanner sc, int n) { HashMap<Integer, Node> map = new HashMap<>(); int rootVal = sc.nextInt(); Node root = new Node(rootVal); map.put(rootVal, root); for (int i = 0; i < n; i++) { int nodeVal = sc.nextInt(); int leftVal = sc.nextInt(); int rightVal = sc.nextInt(); if (map.containsKey(nodeVal)) { Node tmpNode = map.get(nodeVal); Node leftNode = leftVal == 0 ? null : new Node(leftVal); Node rightNode = rightVal == 0 ? null : new Node(rightVal); tmpNode.left = leftNode; tmpNode.right = rightNode; if (leftVal != 0) map.put(leftVal, leftNode); if (rightVal != 0) map.put(rightVal, rightNode); } } return root; } /* //此方法时间复杂度为O(N^2), 因为要以n个点为头, //且每次找最大拓扑结构都需要查找O(N)个节点. public static int returnSize(Node head) { if (head == null) return 0; //假设拓扑结构也以整棵树头节点为头节点,找出最大符合二叉树的拓扑结构 int max = maxTopo(head, head); //接着以每一个节点为头找最大结构 max = Math.max(returnSize(head.left), max); max = Math.max(returnSize(head.right), max); return max; } //找到以h为头节点的树***有多少个节点符合BST结构 public static int maxTopo(Node head, Node node) { if (head != null && node != null && isBSTNode(head, node)) return maxTopo(head, node.left) + maxTopo(head, node.right) + 1; return 0; } //判断以head为头节点的树种node是不是一个可用的BST节点 public static boolean isBSTNode (Node head, Node node) { if (head == null) return false; if (head == node) return true; return isBSTNode(head.val > node.val ? head.left : head.right, node); } */ /*此方法时间复杂度为O(N)。主旨是对任何一个节点,遍历这个节点的左子树的右边界和 右子树的左边界。所有右边界和左边界的所有节点数量为O(N), 所有遍历的代价为O(N),所以 方法时间复杂度为O(N). */ //把节点与贡献值对应 public static int returnSize(Node head) { Map<Node, Record> map = new HashMap<Node, Record>(); return posOrder(head, map); } //后序遍历返回以head为头节点的树的所有子树中最大二叉树拓扑结构的节点数量 public static int posOrder (Node head, Map<Node, Record> map) { if (head == null) { return 0; } //先获得head左右子树上最大二叉树拓扑结构节点数 int ls = posOrder(head.left, map); int rs = posOrder(head.right, map); //然后修改map,看以head为头时还有多少个有效节点 modifyMap(head.left, head, map, true); modifyMap(head.right, head, map, false); //lr和rr分别记录以head左孩子和右孩子为头的左右二叉树, //这两棵二叉树的左右子树分别能给自己提供多少个有效节点 Record lr = map.get(head.left); Record rr = map.get(head.right); //左右孩子整体能提供多少的有效节点 int lbst = lr == null ? 0 : lr.l + lr.r + 1; int rbst = rr == null ? 0 : rr.l + rr.r + 1; map.put(head, new Record(lbst, rbst)); //返回包括head的整个子树最多能提供多少个有效节点 return Math.max(Math.max(ls, rs), lbst + rbst + 1); } //isLeft表示node节点是否在parent的左子树上 //返回的值表示有几个node需要被忽略(无效node) public static int modifyMap(Node child, Node parent, Map<Node, Record> m, boolean isLeft) { if (child == null || (!m.containsKey(child))) return 0; Record r = m.get(child); //当node无法作为以parent为头的树的有效节点时 if ((isLeft && child.val > parent.val) || (!isLeft) && child.val < parent.val) { //一旦当前child违反规则了,则不用再考虑它以及它的所有孩子们了,从map中移除掉 //同时告诉我以它为头节点的整棵二叉树有多少个node m.remove(child); return r.l +r.r + 1; } else { /*若当前child点是否为有效节点,看当前节点在head的左子树上还是右子树上 若在左子树上,child的左孩子们就都不用再查了,肯定都比head小,所以查child的右孩子; 若在右子树上则child右孩子们都不用再查了,肯定都比head大,所以查child的左孩子。 */ int minus = modifyMap(isLeft ? child.right : child.left, parent, m, isLeft); if (isLeft) r.r = r.r - minus; else r.l = r.l - minus; m.put(child, r); return minus; } } }
#include<bits/stdc++.h> using namespace std; bool isBST(int root,int target,int* lc,int* rc) { if(!root) return false; if(root==target) return true; return isBST(root > target ? lc[root]:rc[root],target,lc,rc); } int maxTopo(int root_1,int root_2,int* lc,int* rc) { if(root_1 && root_2 && isBST(root_1,root_2,lc,rc)) return maxTopo(root_1,lc[root_2],lc,rc) + maxTopo(root_1,rc[root_2],lc,rc) + 1; return 0; } void visit(int root,int* lc,int* rc,int& ans) { if(!root) return; ans = max(ans,maxTopo(root,root,lc,rc)); visit(lc[root],lc,rc,ans); visit(rc[root],lc,rc,ans); } int main() { int n,root; cin>>n>>root; int p; int* lc = new int[n+1]; int* rc = new int[n+1]; for(int i=0;i<n;++i) { cin>>p; cin>>lc[p]>>rc[p]; } int ans = 0; visit(root,lc,rc,ans); cout<<ans<<endl; return 0; }