0897. Increasing Order Search Tree

题目信息

题号:

0897

难度:

Easy

主题:

二叉搜索树、节点重排、递增链

原题:

LeetCode 0897

重点:

使用原树全部节点重新连接,最小值节点成为根;每个节点左孩子必须为空,只能通过右孩子按值严格递增

题目重述

给定一棵二叉搜索树 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]
解释:节点数达到允许的最小值,唯一节点已经是最左节点,也没有左右孩子,因此结果树不变。