关于java:LC-2096-StepByStep-Directions-From-a-BT-Node-to-Another

Medium
Google, Amazon, Microsoft, Tiktok
https://leetcode.com/problems…
办法一，
两遍 BFS，第一遍结构 parent 表，同时定位到 start 节点和 end 节点，第二遍从 start 节点 BFS，找到 end 节点，同时保留门路，该办法超时。

class Pair {
    TreeNode node;
    String path;
    public Pair(TreeNode node, String path) {
        this.node = node;
        this.path = path;
    }
}
class Solution {public String getDirections(TreeNode root, int startValue, int destValue) {Map<TreeNode, TreeNode> parent = new HashMap<>();
        parent.put(root, null);
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode start = null, end = null;
        while (!q.isEmpty()) {TreeNode cur = q.poll();
            if (cur.val == startValue) start = cur;
            if (cur.val == destValue) end = cur;
            if (cur.left != null) {parent.put(cur.left, cur);
                q.offer(cur.left);
            }
            if (cur.right != null) {parent.put(cur.right, cur);
                q.offer(cur.right);
            }
        }

        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(start, ""));
        while (!queue.isEmpty()) {Pair cur = queue.poll();
            if (cur.node == end) return cur.path;
            TreeNode parentNode = parent.get(cur.node);
            if (parentNode != null) queue.offer(new Pair(parentNode, cur.path + "U"));
            TreeNode leftNode = cur.node.left;
            if (leftNode != null) queue.offer(new Pair(leftNode, cur.path + "L"));
            TreeNode rightNode = cur.node.right;
            if (rightNode != null) queue.offer(new Pair(rightNode, cur.path + "R"));
        }
        return null;
    }
}

办法二，
组合应用三个小算法，LCA 找最低公共先人，从一个 node 到另一个 node 找门路，结构总门路。

class TreeNode {
    TreeNode left, right;
    int val;

    public TreeNode(int val) {this.val = val;}
}

public class LC2096 {public String getDirections(TreeNode root, int start, int end) {
        // 找 lca
        TreeNode lca = lca(root, start, end);
        // 别离结构 LCA 到 start 和 LCA 到 end 的门路
        List<Character> pathFromLcaToStart = new ArrayList<>();
        List<Character> pathFromLcaToEnd = new ArrayList<>();
        buildPath(lca, start, pathFromLcaToStart);
        buildPath(lca, end, pathFromLcaToEnd);
        StringBuilder res = new StringBuilder();
        // 合并总门路，LCA-start 须要一路逆回去，全部都是 U
        res.append("U".repeat(pathFromLcaToStart.size()));
        for (char character : pathFromLcaToEnd) res.append(character);
        return res.toString();}

    private boolean buildPath(TreeNode node, int target, List<Character> path) {if (node == null) return false;
        if (node.val == target) return true;
        if (node.left != null) {path.add('L');
            if (buildPath(node.left, target, path)) return true;
            path.remove(path.size() - 1);
        }
        if (node.right != null) {path.add('R');
            if (buildPath(node.right, target, path)) return true;
            path.remove(path.size() - 1);
        }
        return false;
    }

    private TreeNode lca(TreeNode root, int start, int end) {if (root == null || root.val == start || root.val == end) return root;
        TreeNode left = lca(root.left, start, end);
        TreeNode right = lca(root.right, start, end);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}