Question
ルート・ノード root と目標値 V を持つバイナリ・サーチ・ツリーが与えられたとき，ツリーを2つのサブツリーに分割し，一方のサブツリーはすべて目標値より小さいか等しいノードを持ち，もう一方のサブツリーはすべて目標値より大きいノードを持つようにします．一方のサブツリーには目標値より小さいか等しいノードがすべてあり、もう一方のサブツリーには目標値より大きいノードがすべてあります。 必ずしも、ツリーに値 V のノードを含むとは限りません。
さらに、元のツリーの構造はほとんど残っているはずです。 正式には、元のツリーで親Pを持つ子Cが、分割後も同じサブツリーにある場合、ノードCは親Pを持つはずです。形式的には、元のツリーで親Pを持つ任意の子Cについて、分割後にそれらが両方とも同じサブツリーにある場合、ノードCはまだ親Pを持つべきです。
分割後、両方のサブツリーのルートTreeNodeを任意の順序で出力する必要があります。
例1.
4
/ \
2 6
/ \ / \
1 3 5 7
一方、出力のダイアグラムは
4
/ \
3 6 and 2
/ \ /
5 7 1
Answer:
class Solution:
def splitBST(self, root: TreeNode, V: int) -> List[TreeNode]:
if not root:
return [None, None]
if root.val <= V:
left, right = self.splitBST(root.right, V)
root.right = left
return [root, right]
else:
left, right = self.splitBST(root.left, V)
root.left = right
return [left, root]
