バイナリ・ツリーが与えられたら、それをその場で1つのリンクされたテーブルに展開します。
例えば
1
/ \
2 5
/ \ \
3 4 6
と拡大してください：
1
\
2
\
3
\
4
\
5
\
6
題意
- バイナリツリーのすべての右ノードをルートノードの右側に配置
- つまり、あるノードに左右両方のノードが存在する場合、左のノードが最初に右のノードに追加されます。
- 予約注文
推論
- 左側のすべてのノードを再帰的に展開し、順番に追加します。
- 展開されたノードはそれ自身の子ノードを含み、再定義が必要です。
- left -> null
- right -> 次に追加される右ノード。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function (root) {
// 特殊なケース：渡されたバイナリツリーが空で、直接返される
if (!root || root.length === 0) {
return root
}
let list = []
helper(root)
// すべてのノードを反復する
for (let i = 0; i < list.length - 1; i++) {
let node = list[i],
nextNode = list[i + 1]
node.left = null
node.right = nextNode
}
// コレクション・ノード
function helper(node) {
if (node !== null) {
list.push(node)
helper(node.left)
helper(node.right)
}
}
}
その他のソリューション
- 再帰中にすべてのノードを走査済み
- 次に、実際のリストを生成することなく、探索中にバイナリツリーをスプライスすることができます。
- 左から右
- ルート・ノードから左のノードにトラバースするときは、左のノードをトラバースして、次のノードである右のノードに挿入します。
1
/ \
2 5
/ \ \
3 4 6
----------------------=>
1
\
2
/ \
3 4
\
5
\
6
----------------------=>
1
\
2
\
3
\
4
\
5
\
6
var flatten = function (root) {
// 特殊なケース：渡されたバイナリツリーが空で、直接返される
if (!root || root.length === 0) {
return root
}
function helper(node) {
if (node !== null) {
// ポイント・ライト・ノード
let right = node.right
// 左ノードを右ノードに置く 左ノードをクリアする，
node.right = node.left
node.left = null
// 現在点の元の左ノードの右ノードのルートを繰り返し、残りの現在点のRIGHTノードが接続されるようにする。
let rightEnd = node
while (rightEnd.right) {
rightEnd = rightEnd.right
}
rightEnd.right = right
// スプライスの右側には、スプライスに続く枝がある。
helper(node.right)
}
}
helper(root)
}
ブログ：
出版：The Pit's Little Bookie
