难度: Easy
给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：
输入：root = [5,1,7] 输出：[1,null,5,null,7]
提示：
[1, 100]0 <= Node.val <= 1000运行时间: 44 ms
内存: 15 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
stack = []
dummy = TreeNode()
t = dummy
while root is not None or len(stack) > 0:
if root is not None:
stack.append(root)
root = root.left
else:
root = stack.pop()
t.right = root
t = t.right
t.left = None
root = root.right
return dummy.right
此题解采用了中序遍历的迭代方法来重构二叉搜索树，使之变成递增顺序搜索树。具体来说，使用一个栈来帮助模拟递归过程的中序遍历。首先，将根节点及其所有左侧子节点推入栈中直到左叶节点。然后，逐个将节点从栈中弹出，这些节点就是按递增顺序访问的。对于每个弹出的节点，使其成为当前最新节点的右子节点，并移除其左子节点，以确保不再有左子节点。这个过程持续进行直到所有节点都被重新链接为一个只有右子节点的链表。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
stack = [] # 栈用于存储节点，以模拟中序遍历
dummy = TreeNode() # 哑节点作为新树的根节点前驱
t = dummy # t是当前处理的节点，初始指向哑节点
while root is not None or len(stack) > 0: # 当还有节点要处理时
if root is not None: # 如果当前节点非空，推入栈中，并进入左子树
stack.append(root)
root = root.left
else: # 否则，从栈中弹出节点，处理当前节点，使之成为新树的一部分
root = stack.pop()
t.right = root # 设置当前节点为上一个处理节点的右子节点
t = t.right # 移动当前节点指针
t.left = None # 清除左子节点链接
root = root.right # 进入右子树
return dummy.right # 返回新树的根节点
在中序遍历的过程中，如果遇到的节点没有左子树，我们应该直接处理该节点。首先，该节点会从栈中弹出，然后按照递增顺序搜索树的构建规则，将该节点作为当前处理的节点的右子节点，并清除该节点的左子链接。然后继续检查该节点的右子树，如果存在，进一步按照中序遍历的顺序进入右子树进行遍历。
哑节点（dummy node）在这个算法中作为新树的前驱使用，主要是为了方便地构建和返回新树。哑节点本身不存储任何有效数据，其右子节点指向新树的根节点。这样做的好处是在遍历和重构过程中，我们可以使用一个持续更新的指针（在这里是变量`t`），而始终保持哑节点作为参照点，最终通过返回哑节点的右子节点，即可得到完整的新树根节点。这样可以避免处理特殊的边界情况，如树的根节点可能会变化的情况。
在从栈中弹出节点处理过程中，将弹出节点的左子节点设为None是为了确保新构建的递增顺序搜索树满足其定义，即每个节点都只有右子节点，没有左子节点。这样做也有助于防止在后续的遍历中重新访问已经处理过的左子树，从而避免造成无限循环或重复处理节点。
该算法在处理有重复值的节点时仍然有效。在二叉搜索树中，即使有重复值，这些值也会按照特定的顺序存储，通常是重复值全部存储在相等值的一侧（通常是右侧）。中序遍历会按照从小到大的顺序访问这些值，包括重复值，因此重复值会按照它们在树中的排列顺序被连续访问。最终，这些重复值会在新树中以连续的右子节点的形式出现，不会影响算法的执行和结果的正确性。