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; }}