我正在嘗試解決一個問題：在二叉樹中查找特定節點的所有祖先。
Input: root, targetNode
Output: An array/list containing the ancestors
假設，我們以上面的二叉樹為例。我們要找到節點 4 的祖先。輸出應該是 [3, 5, 2, 4]。如果節點為 8，則輸出為 [3, 1, 8]
為了解決這個問題，我撰寫了一個實作 DFS 的函式。
var ancestor = function(root, target) {
var isFound = false;
const dfs = (node, curr) => {
if (node === null) {
return curr;
}
if (node.val === target.val) {
curr.push(node.val);
isFound = true;
return curr;
}
curr.push(node.val);
const left = dfs(node.left, curr);
if (!isFound) {
const right = dfs(node.right, curr);
curr.pop();
return right;
} else {
curr.pop();
return left;
}
}
console.log(dfs(root, []));
};
但它沒有回傳正確的輸出。例如，如果targetNode 為7，則輸出為[3]，如果targetNode 為8，則輸出也為[3]。如果我洗掉該行curr.pop()，輸出也無效。對于 targetNode 7，它是 [3, 5, 6, 2, 7]。我想我發現了我犯錯的問題。在回溯時，我在洗掉curr陣列中推送的節點時做錯了。如果我傳遞一個字串而不是陣列，它會正確列印輸出。
var ancestor = function(root, target) {
var isFound = false;
const dfs = (node, curr) => {
if (node === null) {
return curr;
}
if (node.val === target.val) {
curr = node.val;
isFound = true;
return curr;
}
const left = dfs(node.left, curr node.val '->);
if (!isFound) {
const right = dfs(node.right, curr node.val '->);
return right;
} else {
return left;
}
}
console.log(dfs(root, ''));
上面帶有字串而不是陣列的代碼正確列印輸出，如果我通過 targetNode 7，輸出是3->5->2->7
我的問題是，如何在這里正確取消選擇/回溯？或者還有什么我做錯的嗎？提前致謝。
uj5u.com熱心網友回復：
自然環境中的遞回
遞回是一種函式式遺產，因此以函式式風格使用它會產生最好的結果。這意味著避免必要的事情，例如像pushand這樣的突變，像 那樣的cur = node.val變數重新分配isFound = true，以及其他副作用。我們可以撰寫ancestor一個簡單的基于生成器的函式，將每個節點添加到遞回子問題的輸出中 -
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function* ancestor(t, q) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of ancestor(t.left, q)) yield [t.val, ...l]
for (const r of ancestor(t.right, q)) yield [t.val, ...r]
}
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
for (const path of ancestor(mytree, 7))
console.log(path.join("->"))3->5->2->7
使用模塊
最后，我會為此代碼推薦一種基于模塊的方法 -
// tree.js
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function* ancestor(t, q) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of ancestor(t.left, q)) yield [t.val, ...l]
for (const r of ancestor(t.right, q)) yield [t.val, ...r]
}
function insert(t, val) {
// ...
}
function remove(t, val) {
// ...
}
function fromArray(a) {
// ...
}
// other tree functions...
export { empty, node, ancestor, insert, remove, fromArray }
// main.js
import { node, ancestor } from "./tree.js"
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
for (const path of ancestor(mytree, 7))
console.log(path.join("->"))
3->5->2->7
私人發電機
在前面的實作中，我們的模塊為ancestor的公共介面公開了一個生成器。另一種選擇是undefined在找不到節點并且沒有祖先時回傳。考慮這個隱藏生成器并要求呼叫者對結果進行空檢查的替代實作 -
const empty =
Symbol("tree.empty")
function node(val, left = empty, right = empty) {
return { val, left, right }
}
function ancestor(t, q) {
function* dfs(t) {
if (t == empty) return
if (t.val == q) yield [t.val]
for (const l of dfs(t.left)) yield [t.val, ...l]
for (const r of dfs(t.right)) yield [t.val, ...r]
}
return Array.from(dfs(t))[0]
}
const mytree =
node(3, node(5, node(6), node(2, node(7), node(4))), node(1, node(0), node(8)))
const result =
ancestor(mytree, 7)
if (result)
console.log(result.join("->"))
else
console.log("no result")3->5->2->7
uj5u.com熱心網友回復：
您需要檢查右孩子的DFS是否找到了該節點。使固定：
const left = dfs(node.left, curr);
if (!isFound) {
const right = dfs(node.right, curr);
if(isFound) {
return right;
}
curr.pop();
return; // return nothing, backtracking
}
return left;
uj5u.com熱心網友回復：
在陣列示例中，您的回圈以 DFS 方式遍歷節點，因此每個節點都以這種方式連接。如果我們計算 DFS 演算法中的樹節點， [3 , 5, 6, 2, 7] 實際上是按 1, 2, 3, 4 和 5 的順序排列的。 這樣，陣列中的整個樹應該看起來像這樣; [3, 5, 6, 2, 7, 4, 1, 0, 8]。
因此，當您找到目標值時，您從當前節點彈出并在 DFS 演算法中將其全部追溯到頭節點。
我要么建議找到一種方法來解決這個問題，要么你可以保存每個節點的父節點。這意味著您可以使用元組而不是 int 陣列（如果可以接受的話）。索引可能如下所示 = (節點值，父值)
[(3,NULL),(5,3),(6,5),(2,5)...]
然后相應地回溯......
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/356395.html
下一篇：Scala遞回/尾遞回