リートコード 776 - BSTを分割する

ルート・ノード root と目標値 V を持つバイナリ・サーチ・ツリーが与えられたとき，ツリーを2つのサブツリーに分割し，一方のサブツリーはすべて目標値より小さいか等しいノードを持ち，もう一方のサブツリーはすべて目標値より大きいノードを持つようにします．一方のサブツリーには目標値より小さいか等しいノードがすべてあり、もう一方のサブツリーには目標値より大きいノードがすべてあります。 必ずしも、ツリーに値 V のノードを含むとは限りません。

さらに、元のツリーの構造はほとんど残っているはずです。 正式には、元のツリーで親Pを持つ子Cが、分割後も同じサブツリーにある場合、ノードCは親Pを持つはずです。形式的には、元のツリーで親Pを持つ任意の子Cについて、分割後にそれらが両方とも同じサブツリーにある場合、ノードCはまだ親Pを持つべきです。

分割後、両方のサブツリーのルートTreeNodeを任意の順序で出力する必要があります。

例1.

Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Explanation:
Note that root, output[0], and output[1] are TreeNode objects, not arrays.
The given tree [4,2,6,1,3,5,7] is represented by the following diagram:
 4
 / \
 2 6
 / \ / \
 1 3 5 7
while the diagrams for the outputs are:
 4
 / \
 3 6 and 2
 / \ /
 5 7 1

注。

1. The size of the BST will not exceed .

2. The BST is always valid and each node's value is different.

   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]