0776：拆分二叉搜索树（★★）

力扣第 776 题

题目

给你一棵二叉搜索树（BST）的根结点 root 和一个整数 target 。请将该树按要求拆分为两个子树：其中一个子树结点的值都必须小于等于给定的目标值；另一个子树结点的值都必须大于目标值；树中并非一定要存在值为 target 的结点。

除此之外，树中大部分结构都需要保留，也就是说原始树中父节点 p 的任意子节点 c ，假如拆分后它们仍在同一个子树中，那么结点 p 应仍为 c 的父结点。

返回 两个子树的根结点的数组 。

示例 1：

输入：root = [4,2,6,1,3,5,7], target = 2
输出：[[2,1],[4,3,6,null,null,5,7]]

示例 2:

输入: root = [1], target = 1
输出: [[1],[]]

提示：

• 二叉搜索树节点个数在 [1, 50] 范围内
• 0 <= Node.val, target <= 1000

分析

按根节点是否大于 target 递归即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def splitBST(self, root: Optional[TreeNode], target: int) -> List[Optional[TreeNode]]:
	def dfs(node):
		if not node:
			return [None,None]
		if node.val<=target:
			l,r = dfs(node.right)
			node.right=l
			return [node,r]
		l,r = dfs(node.left)
		node.left = r
		return [l, node]

	return dfs(root)

48 ms