Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
2096. Step-By-Step Directions From a Binary Tree Node to Another
給你一個二元樹的根節點以及startValue、destValue，你可以往上、往右、往左移動，求
出startValue到destValue的最短路徑要怎麼走。
思路：
1.先用DFS建一個包含父親節點的圖。
2.最短路徑我是想BFS，用BFS從startValue開始走，走過的點不走然後第一次碰到
destValue的路徑必定最短。
java code:
------------------------------------------------------
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue)
{
Set<Integer> visited = new HashSet<>();
Map<Integer, TreeNode[]> graph = new HashMap<>();
String dir = "LRU";
// traversal
dfs(graph, root, null);
// BFS
Queue<Recored> queue = new LinkedList<>();
queue.add(new Recored(startValue, ""));
while (!queue.isEmpty()) {
Recored curr = queue.poll();
int id = curr.id;
TreeNode[] relation = graph.get(id);
// 找到
if (id == destValue) {
return curr.step;
}
for (int i = 0; i < 3; i++) {
if (relation[i] != null &&
!visited.contains(relation[i].val)) {
visited.add(relation[i].val);
queue.add(new Recored(relation[i].val, curr.step +
dir.charAt(i)));
}
}
}
return "";
}
void dfs(Map<Integer, TreeNode[]> graph, TreeNode root, TreeNode prev) {
if (root == null) {
return;
}
TreeNode[] relation = new TreeNode[3];
relation[0] = root.left;
relation[1] = root.right;
relation[2] = prev;
graph.put(root.val, relation);
dfs(graph, root.left, root);
dfs(graph, root.right, root);
}
}
class Recored {
String step;
int id;
public Recored(int id, String step) {
this.step = step;
this.id = id;
}
}
------------------------------------------------------
847 ms
Beats 5.65%
姆咪這輩子就這樣了
哀
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721103249.A.CE1.html
※ 編輯: Rushia (122.100.73.13 臺灣), 07/16/2024 12:19:22
推
07/16 12:42,
1年前
, 1F
07/16 12:42, 1F
討論串 (同標題文章)
完整討論串 (本文為第 505 之 1548 篇)：