LeetCode2096二叉树节点间路径方向BFS求解错误问题排查

我在尝试解决LeetCode题目 2096. Step-By-Step Directions From a Binary Tree Node to Another，题目要求如下：

给定包含n个节点的**二叉树（binary tree）**的root根节点，每个节点被唯一分配1到n范围内的值。同时给定代表起始节点s值的整数startValue，以及代表目标节点t值的不同整数destValue。

请找出从节点s到节点t的最短路径（shortest path），将路径的逐步行进方向生成为仅包含大写字母'L'、'R'、'U'的字符串，各字母含义为：

• 'L'：从当前节点移动到其左子节点（left child）
• 'R'：从当前节点移动到其右子节点（right child）
• 'U'：从当前节点移动到其父节点（parent）

返回节点s到节点t最短路径的逐步行进方向字符串。

我的实现思路是先通过邻接表将树转换为图结构，为每个节点存储相邻节点及对应移动方向。例如对于树[1,2,3]，遍历完成后得到的HashMap结构为{1:[(2,'L'), (3,'R')], 2:[(1,'U')], 3:[(1,'U')]}。

我原本认为从起始节点执行BFS即可追踪到目标节点的路径，但实际运行时结果始终错误：若目标节点在左子树但我先遍历右子节点，或先遍历右子节点但目标在左子树时，会出现多余步长。

我参考了通用的BFS路径追踪实现思路，逻辑看似正确，但不清楚哪里存在问题，也不理解路径回溯的作用与必要性。

我的Java实现代码如下：

public class StepByStep {

    HashMap<TreeNode, HashMap<TreeNode, String>> graph = new HashMap<TreeNode, HashMap<TreeNode, String>>();

    public static void main(String argv[]) {
        TreeNode root = new TreeNode (5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(4);
        StepByStep sbs = new StepByStep();
        System.out.println(sbs.getDirections(root, 3, 6));
        Set<TreeNode> keys = sbs.graph.keySet();
        for(TreeNode key : keys) {
            System.out.print(key.val + " ");
            HashMap<TreeNode, String> map = sbs.graph.get(key);
            Set<TreeNode> nodes = map.keySet();
            for(TreeNode node : nodes) {
                System.out.print(node.val + map.get(node) + " ");
            }
            System.out.println();
        }
    }

    public String getDirections(TreeNode root, int startValue, int destValue) {
        // 中序遍历构建邻接表
        inorder(root, null);
        // 基于邻接表执行广度优先搜索
        Set<TreeNode> keys = graph.keySet();
        TreeNode start = null;
        for(TreeNode key : keys) {
            if(key.val == startValue) {
                start = key;
                break;
            }
        }
        return bfs(start, destValue);
    }
    
    public String bfs(TreeNode root, int destValue) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        queue.add(root);
        StringBuilder sb = new StringBuilder("");
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                TreeNode current = queue.poll();
                if(current.val == destValue) {
                    return sb.toString();
                }
                visited.add(current);
                HashMap<TreeNode, String> map = graph.get(current);
                Set<TreeNode> keys = map.keySet();
                for(TreeNode key : keys) {
                    if(!visited.contains(key)) {
                        sb.append(map.get(key));
                        queue.add(key);
                    }
                }
                --size;
            }
        }
        return "";
    }

    public void inorder(TreeNode root, TreeNode parent) {
        if (root == null)
            return;
        inorder(root.left, root);
        inorder(root.right, root);
        if (root.left != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(root.left, "L");
            graph.put(root, map);
        }
        if (root.right != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(root.right, "R");
            graph.put(root, map);
        }
        if (parent != null) {
            if (!graph.containsKey(root)) {
                graph.put(root, new HashMap<TreeNode, String>());
            }
            HashMap<TreeNode, String> map = graph.get(root);
            map.put(parent, "U");
            graph.put(root, map);
        }
    }
}

请问我的实现存在什么问题？

内容的提问来源于stack exchange，提问作者Spindoctor