我正在嘗試解決 LeetCode 問題2096。從二叉樹節點到另一個節點的逐步指導：
給你
root一個帶有節點的二叉樹。n每個節點都被唯一地分配一個從1到的值n。您還將獲得一個startValue表示起始節點值的整數，以及一個表示目標節點值的s不同整數。destValuet找到從節點開始到節點結束的最短路徑。將此類路徑的逐步方向生成為僅由大寫字母、和組成的字串。每個字母表示一個特定的方向：
st'L''R''U'
'L'意思是從一個節點到它的左子節點。'R'意思是從一個節點到它的右子節點。'U'意思是從一個節點到它的父節點。回傳從 node到 node的最短路徑的逐步方向
st。
我已經使用鄰接串列將樹轉換為圖形。對于每個節點，我存盤相鄰節點以及方向。例如，假設我們有一棵樹[1,2,3]，那么在遍歷結束時，我們得到一個看起來像 的 HashMap {1:[(2,'L'), (3,'R')], 2:[(1,'U')], 3:[(1,'U')]。
我假設從 startNode 到 endNode 執行 BFS 將幫助我跟蹤路徑。但是，如果 endNode 在左側但我先嘗試了正確的節點，或者我先嘗試了正確的節點并且 endNode 離開了，我最終會得到一個不正確的答案或額外的步驟。
我在 Stack Overflow如何跟蹤廣度優先搜索中的路徑？看來我的方法似乎是正確的（我不知道我錯過了什么）。我也不明白回溯的目的或需要。
我的代碼如下：
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) {
// we do a inorder traversal
inorder(root, null);
//now we perform a breadth first search using the graph
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);
}
}
}
我錯過了什么？
uj5u.com熱心網友回復：
問題在于bfs：您將每個訪問過的節點都添加到sb，但這是錯誤的，因為這些節點并不都在從根到該特定節點的路徑上。相反，您應該考慮每個訪問過的節點都代表它自己從根開始的唯一路徑，它不包括所有已經訪問過的節點，只是其中的幾個。
一種解決方案是，您不僅將節點存盤在佇列中，還將其自己的移動字串（如其私有sb）存盤在佇列中，以便您實際上在佇列中存盤一個 Pair：一個節點和一個字串緩沖區。
找到目的地后，您可以回傳該特定字串。
或者，如果您執行深度優先搜索（使用遞回），在回溯時構建字串，您會更輕松。這將花費更少的記憶體。當您需要找到最短路徑時，廣度優先很有趣，但是在樹中，兩個節點之間只有一條路徑，因此找到任何路徑都足夠好，這就是深度優先搜索將為您提供的。
最后，我將解決這個問題如下：
執行深度優先遍歷，并收集從根到起始節點的步驟（“L”或“R”）以及從根到目標節點的步驟。這些路徑只有字母“L”和“R”，因為沒有向上運動。
從這些路徑中洗掉公共前綴，以便兩條路徑現在都從它們最低的公共祖先節點開始。
將第一條路徑的所有字母（如果有）替換為“U”。
完畢。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/486740.html
上一篇：確定兩個圖是否相同的演算法