0897. Increasing Order Search Tree¶
题目信息¶
- 题号:
0897
- 难度:
Easy
- 主题:
二叉搜索树、节点重排、递增链
- 原题:
- 重点:
使用原树全部节点重新连接,最小值节点成为根;每个节点左孩子必须为空,只能通过右孩子按值严格递增
题目重述¶
给定一棵二叉搜索树 root。按照中序遍历的顺序重新连接树中的全部节点,使结果树的根节点是原树最左侧、也就是值最小的节点,并且每个节点都没有左孩子,只有可能存在一个右孩子。
沿结果树的右孩子链读取时,节点值按非递减顺序排列,并且原树中的每个节点恰好出现一次。请返回重排后树的根节点。
树中节点数在 [1, 100] 范围内,0 <= Node.val <= 1000。
自建示例¶
分布在多层的节点被连接成递增右链:
输入:root = [7,4,9,2,5,8,10]
输出:[2,null,4,null,5,null,7,null,8,null,9,null,10]
解释:原树的中序遍历为 2、4、5、7、8、9、10。重排后值 2 的节点成为根,其余节点依次作为右孩子,所有左孩子都为空。
树只有一个节点:
输入:root = [0]
输出:[0]
解释:节点数达到允许的最小值,唯一节点已经是最左节点,也没有左右孩子,因此结果树不变。