是否可以在 O(m n 1) 時間內合并滿足堆順序的兩棵樹？而 m 和 n 是輸入樹的高度。
Example
Input:
10 8
\
9
Output: (Can be any one of them)
10 10 10 10
\ / \ / \ /
9 9 8 8 9 9
/ /
8 8
uj5u.com熱心網友回復：
是的，這可以在 O(?? ??) 中完成，條件是允許輸出樹與輸入樹共享節點。
演算法
給定兩個根節點a和b：
- 如果
a和b都為空，則回傳空（基本情況） - 如果其中一個為空，則選擇另一個。否則選擇具有較大值的節點。讓我們假設這
a是選定的節點。 - 創建一個
x與ahas值相同的新節點。 - 執行遞回合并
a.left和b。將合并的結果附加到x.left - 將未
a.right更改的參考分配給x.right - 回傳
x
由于在遞回的每一級，我們都降低了主題中一棵樹的高度，遞回深度最多是兩棵輸入樹的高度之和，從它遵循給定的時間復雜度。
在步驟 3 中合并a.left或合并的選擇a.right是任意的。你可以讓它隨機。
示例實作
這是 JavaScript 的粗略實作。運行此代碼段時，將合并以下兩棵樹：
10 8
/ \ / \
4 9 7 6
/ \ / \ \
3 1 2 5 0
class Node {
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
toString() {
return (this.right ? this.right.toString().replace(/^/gm, " ") "\n" : "")
this.value
(this.left ? "\n" this.left.toString().replace(/^/gm, " ") : "");
}
}
function merge(a, b) {
if (a == null && b == null) return null;
if (a == null || (b != null && b.value > a.value)) {
return new Node(b.value, merge(a, b.left), b.right);
}
return new Node(a.value, a.left, merge(b, a.right));
}
// Example
let a = new Node(10,
new Node(4,
new Node(3),
new Node(1)
),
new Node(9,
new Node(2),
new Node(5)
)
);
let b = new Node(8,
new Node(7),
new Node(6,
null,
new Node(0)
)
);
console.log("a:");
console.log(a.toString());
console.log("b:");
console.log(b.toString());
console.log("merged:");
console.log(merge(a, b).toString());這個片段有一個非常基本的列印功能——它列印旋轉 90° 的樹，根在左側。沒有連接節點的線（你必須想象它們），只是縮進。
該示例將生成這棵樹：
10
/ \
4 9
/ \ / \
3 1 8 5
/ \
7 6
/ \
2 0
注意：你提到了 O(?? ?? 1)，但是這個額外的常數是無關緊要的：O(?? ?? 1) = O(?? ??)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359130.html
上一篇：LeetCode的時間復雜度3.無重復字符的最長子串
下一篇：開始迷宮的細胞