アルゴリズム_各ノードの次の右側のポインタを埋める#
すべての葉が同じレベルにある完全な二分木が与えられます。また、すべての親ノードには 2 つの子があります。この二分木は次の定義を持っています：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
各 next ポインタを次の右側のノードを指すように埋めてください。次の右側のノードが存在しない場合、next ポインタは NULL に設定されます。
最初は、すべての next ポインタが NULL に設定されています。
例 1：
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
説明：上記の完全な二分木（図 A）が与えられた場合、関数は各 next ポインタを次の右側のノードに指すように埋める必要があります。シリアル化された出力は、次のポインタによって接続されたレベル順のものであり、'#' は各レベルの終わりを示しています。
例 2：
Input: root = []
Output: []
解法#
この問題は理解できませんでしたので、解法を見ても理解できず、ビデオを探しました。POPULATING NEXT RIGHT POINTERS IN EACH NODE (Leetcode) - Code & Whiteboardというビデオを見つけました。ビデオでは Python のコードが説明されていますが、ロジックは非常に明確で、Swift に翻訳することもできます。
簡単に理解すると：
- 完全な二分木なので、left が存在する場合は必ず right も存在するため、ノードを走査する際に node.left の存在を確認するだけで、次のレベルがあるかどうかがわかります。
- すべての next ポインタは NULL に設定されていますので、ノードの next は最初は nil です。
- 同じ親ノードの left と right の関係を設定するため、node.left.next = node.right のように設定します。例えば、2 と 3、4 と 5、6 と 7 の関係です。
- 異なる親ノードの関係を設定する場合は、親ノードの next の存在を確認する必要があります。存在する場合は、node.right.next = node.next.left のように設定します。例えば、5 と 6 の関係です。
以下はコードです：
/**
* Definition for a Node.
* public class Node {
* public var val: Int
* public var left: Node?
* public var right: Node?
* public var next: Node?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* self.next = nil
* }
* }
*/
class Solution {
func connect(_ root: Node?) -> Node? {
// エラーチェック
if root == nil {
return nil
}
var leftMostNode = root
// leftをループ
while (leftMostNode?.left != nil) {
var cur = leftMostNode
while (cur?.left != nil) {
cur?.left?.next = cur?.right
if (cur?.next != nil) {
cur?.right?.next = cur?.next?.left
}
cur = cur?.next
}
leftMostNode = leftMostNode?.left
}
return root
}
}