#1 WA求指点(有注释)
查看原帖
#1 WA求指点(有注释)
1217458
magnolia_楼主2024/12/12 18:06
import java.io.*;
import java.util.*;

public class Main {

    // 定义二叉树的节点结构
    public static class TreeNode {
        TreeNode left; // 左子树
        int val;       // 节点值
        TreeNode right; // 右子树

        // 构造函数,初始化节点值
        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 读取输入的类
    public static class Read {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        // 读取下一个整数
        public int read() throws IOException {
            st.nextToken();
            return (int) st.nval;
        }
    }

    // 根节点
    public static TreeNode root;
    // 存储每个节点的映射关系
    public static HashMap<Integer, TreeNode> nodeMap = new HashMap<>();
    // 深度和宽度
    public static int depth;
    public static int width;

    public static void main(String[] args) throws IOException {
        // 初始化输入读取器和输出打印器
        Read rd = new Read();
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取节点数
        int n = rd.read();

        // 构建二叉树
        for (int i = 0; i < n - 1; i++) {
            int u = rd.read(); // 读取父节点
            int v = rd.read(); // 读取子节点
            addNode(u, v); // 添加节点到树中
        }

        // 读取要求计算距离的两个节点
        int x = rd.read();
        int y = rd.read();
        
        // 计算x和y的最低公共祖先,返回距离
        int distance = findLCA(x, y);
        
        // 使用bfs计算树的深度和宽度
        bfs();

        // 输出深度、宽度和x、y之间的距离
        pw.println(depth);
        pw.println(width);
        pw.print(distance);
        
        // 关闭输出流
        pw.close();
    }

    // 查找从根节点到目标节点的路径
    private static boolean findPath(TreeNode root, int target, ArrayList<TreeNode> path) {
        // 如果当前节点为空,返回false
        if (root == null) {
            return false;
        }

        // 将当前节点加入路径
        path.add(root);

        // 如果当前节点是目标节点,返回true
        if (root.val == target) {
            return true;
        }

        // 否则递归查找左右子树
        if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
            return true;
        }

        // 如果都没找到,移除路径中的当前节点
        path.remove(path.size() - 1);
        return false;
    }

    // 计算节点x和y之间的距离
    public static int findLCA(int x, int y) {
        // 存储节点x和y的路径
        ArrayList<TreeNode> xPath = new ArrayList<>();
        ArrayList<TreeNode> yPath = new ArrayList<>();

        // 查找节点x和y的路径
        findPath(root, x, xPath);
        findPath(root, y, yPath);

        // 查找x和y路径的最低公共祖先(LCA)
        int i;
        for (i = 0; i < Math.min(xPath.size(), yPath.size()); i++) {
            // 遇到不同的节点,退出循环
            if (xPath.get(i) != yPath.get(i)) break;
        }

        // 计算x到LCA的路径长度和y到LCA的路径长度
        int xToLCALength = xPath.size() - i;
        int yToLCALength = yPath.size() - i;

        // 返回x到LCA的路径长度乘2加上y到LCA的路径长度
        return (xToLCALength << 1) + yToLCALength;
    }

    // 添加节点
    public static void addNode(int u, int v) {
        // 如果u和v的节点还未创建,则创建节点
        nodeMap.putIfAbsent(u, new TreeNode(u));
        nodeMap.putIfAbsent(v, new TreeNode(v));
        
        TreeNode parentNode = nodeMap.get(u);
        TreeNode childNode = nodeMap.get(v);

        // 如果root为空,则当前u节点为根节点
        if (root == null) {
            root = parentNode;
        }

        // 为父节点添加子节点
        if (parentNode.left == null) {
            parentNode.left = childNode;
        } else {
            parentNode.right = childNode;
        }
    }

    // 使用BFS遍历树,计算深度和宽度
    public static void bfs() {
        Deque<TreeNode> queue = new ArrayDeque<>();

        // 从根节点开始遍历
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            // 更新宽度
            width = Math.max(width, size);

            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();

                // 将当前节点的左子树和右子树加入队列
                if (poll.left != null) {
                    queue.offer(poll.left);
                }

                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }

            // 更新深度
            depth++;
        }
    }
}

2024/12/12 18:06
加载中...