删除二叉搜索树中的节点

题目描述

给定一棵二叉搜索树的根节点 root 和一个整数 key，请删除二叉搜索树中值为 key 的节点，并返回删除后的根节点。

为保证输出唯一，本题规定当被删除节点同时具有左、右两个子节点时，使用右子树中的最小节点作为后继节点来替换当前节点。

二叉搜索树满足：

• 左子树所有节点值都严格小于当前节点值；
• 右子树所有节点值都严格大于当前节点值；
• 左右子树本身也都是二叉搜索树。

输入格式

第一行输入两个整数 n 和 key，分别表示二叉树层序序列长度和待删除的值。

第二行输入 n 个字符串，表示二叉树的层序遍历结果，其中：

• 非 null 字符串表示该节点的整数值；
• null 表示该位置为空节点。

保证输入序列能够唯一确定一棵二叉搜索树，且根节点非空。

输出格式

输出两行：

第一行输出一个整数 m，表示删除后树的层序序列长度（已去除末尾多余的 null）。

第二行输出 m 个字符串，表示删除后的层序序列。

数据范围

1 <= n <= 10^4

-10^5 <= Node.val, key <= 10^5

节点值互不相同。

样例 1

输入

7 3
5 3 6 2 4 null 7

输出

6
5 4 6 2 null null 7