难度: Easy
给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 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注意：本题与主站 897 题相同： https://leetcode-cn.com/problems/increasing-order-search-tree/
运行时间: 23 ms
内存: 16.0 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:
res = []
def dfs(root):
nonlocal res
if root == None:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
if res == None:
return None
res_root = TreeNode(res[0])
res_root.left = None
cur = res_root
for n in res[1:]:
node = TreeNode(n)
node.left = None
cur.right = node
cur = node
return res_root
此题解采用了中序遍历的方式来遍历二叉搜索树。首先，通过递归的方式对树进行中序遍历，并将遍历的结果存储在一个数组中。然后，使用这个数组来构建一个新的递增顺序搜索树，这个新树的每个节点都只有右子节点，没有左子节点。
时间复杂度: 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:
res = []
def dfs(root):
nonlocal res
if root == None:
return
dfs(root.left)
res.append(root.val) # 将节点值添加到数组中
dfs(root.right)
dfs(root)
if res == None:
return None
res_root = TreeNode(res[0]) # 创建新树的根节点
res_root.left = None
cur = res_root
for n in res[1:]: # 遍历数组，构建新树的右子节点
node = TreeNode(n)
node.left = None
cur.right = node
cur = node
return res_root
在中序遍历中，递归地访问二叉树的左子树，然后处理当前节点（通常是进行一些操作如打印或存储节点值），最后递归地访问右子树。这种方式确保了所有节点都按照左-根-右的顺序被访问。递归的基本案例是检查当前节点是否为空，如果为空，则返回，不进行任何操作。这保证了只有存在的、非空的节点才被处理，从而确保所有节点都被正确且完整地访问。
使用`nonlocal`关键字允许内嵌函数修改封闭作用域中的变量。优点包括：1) 可以直接在内部函数中修改外部变量，使代码更简洁；2) 避免使用全局变量，减少了变量作用域的污染。缺点包括：1) 过度依赖`nonlocal`可能会使得函数的行为变得不那么明显，降低代码的可读性；2) 在复杂的函数嵌套中，修改外部变量可能导致错误难以追踪和调试。
新的递增顺序搜索树实质上是一种只有右子节点的链表结构。这种结构的搜索效率不如传统的二叉搜索树。在传统的二叉搜索树中，每个节点的左右子节点分别小于和大于该节点，这样可以在每个节点处根据搜索值选择向左或向右，有效地减半搜索路径的长度。然而，在只有右子节点的树中，搜索任何值都需要从头到尾遍历整个链表，因此搜索效率为线性时间O(n)，而不是二叉搜索树的对数时间O(log n)。