47. Split BST

読了目安 約2分

Recursion / LeetCode 776 (Medium) — BST を値 V 以下と V 超の 2 つの BST に分割する。Premium 限定。

問題

LeetCode 776. Split BST（Medium / カテゴリ: Recursion）

LeetCode Premium 限定です。問題の要点は次の要約の通りです。

二分探索木（BST）は、どの頂点でも「左部分木の値 < 頂点の値 < 右部分木の値」が成り立つ木です。 その根 root と整数 target が与えられます。

この木を 2 つの BST に分割します。 1 つ目には target 以下の値だけを、2 つ目には target より大きい値だけを入れます。 target が木の中に存在するとは限りません。

元の木で親子だった頂点は、分割後も可能な限り親子関係を保ちます。 答えは「target 以下の木の根」と「target 超の木の根」の 2 要素の配列で返します。 どちらかの木が空（nil）になることもあります。

無料で読める類題: LeetCode 450. Delete Node in a BST。BST の部分木をつなぎ替える操作の練習になります。

考え方

Swift 実装のポイント

• 戻り値の型は [TreeNode?] です。nil を要素に持てる配列で「空の木」を表します。
• TreeNode は class（参照型）なので、root.right = parts[0] のようなつなぎ替えがそのまま木を書き換えます。
• 再帰は境界をまたぐ側の部分木だけを掘り進みます。触る頂点は根から下への 1 本の経路上だけです。
• テストコードは値の振り分けだけでなく、元のノードが再利用されていることと、分割に不要な親子関係が保たれていることも検証します。

class Solution {
    func splitBST(_ root: TreeNode?, _ target: Int) -> [TreeNode?] {
        guard let root = root else { return [nil, nil] }
        if root.val <= target {
            let parts = splitBST(root.right, target)
            root.right = parts[0]
            return [root, parts[1]]
        } else {
            let parts = splitBST(root.left, target)
            root.left = parts[1]
            return [parts[0], root]
        }
    }
}