第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
第 n+2 行输入一个整数 m,表示询问的次数。
以下 m 行每行两个节点 o1 和 o2。
对于每组询问每行输出一个整数表示答案。
8 1 1 2 3 2 4 5 4 0 0 5 0 0 3 6 7 6 0 0 7 8 0 8 0 0 4 4 5 5 2 6 8 5 8
2 2 3 1
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int rootVal = sc.nextInt(); TreeNode root = buildTree(sc, n, rootVal); Record record = new Record(root); int m = sc.nextInt(); StringBuilder cache = new StringBuilder(); while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); cache.append(record.query(u, v)).append("\n"); } System.out.println(cache); } private static TreeNode buildTree(Scanner sc, int n, int rootVal) { Map<Integer, TreeNode> map = new HashMap<>(); while (n-- > 0) { int fa = sc.nextInt(); int lch = sc.nextInt(); int rch = sc.nextInt(); TreeNode faNode = map.get(fa); if (faNode == null) { faNode = new TreeNode(fa); map.put(fa, faNode); } if (lch != 0) { TreeNode lchNode = map.get(lch); if (lchNode == null) { lchNode = new TreeNode(lch); map.put(lch, lchNode); } faNode.left = lchNode; } if (rch != 0) { TreeNode rchNode = map.get(rch); if (rchNode == null) { rchNode = new TreeNode(rch); map.put(rch, rchNode); } faNode.right = rchNode; } } return map.get(rootVal); } } class Record { private Map<Integer, HashMap<Integer, Integer>> map; // a b c: a和b的父节点是c public Record(TreeNode head) { map = new HashMap<>(); initMap(head); setMap(head); } private void initMap(TreeNode head) { if (head == null) { return; } map.put(head.val, new HashMap<>()); initMap(head.left); initMap(head.right); } private void setMap(TreeNode head) { if (head == null) { return; } headRecord(head.left, head); headRecord(head.right, head); subRecord(head); setMap(head.left); setMap(head.right); } private void headRecord(TreeNode son, TreeNode head) { if (son == null) { return; } map.get(son.val).put(head.val, head.val); headRecord(son.left, head); headRecord(son.right, head); } private void subRecord(TreeNode head) { if (head == null) { return; } preLeft(head.left, head.right, head); subRecord(head.left); subRecord(head.right); } private void preLeft(TreeNode left, TreeNode right, TreeNode head) { if (left == null) { return; } preRight(left, right, head); preLeft(left.left, right, head); preLeft(left.right, right, head); } private void preRight(TreeNode left, TreeNode right, TreeNode head) { if (right == null) { return; } map.get(left.val).put(right.val, head.val); preRight(left, right.left, head); preRight(left, right.right, head); } public int query(int o1, int o2) { if (o1 == o2) { return o1; } if (map.containsKey(o1) && map.get(o1).containsKey(o2)) { return map.get(o1).get(o2); } if (map.containsKey(o2) && map.get(o2).containsKey(o1)) { return map.get(o2).get(o1); } return -1; } }