深度优先遍历|LeetCode —— 897. 递增顺序查找树（Python）深度优先遍历|LeetCode算法题

给你一个树，请你按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例：

文章图片

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-order-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
————————
解题思路：使用中序遍历获得递增序列，然后按顺序构建只有右子结点的树：

# Definition for a binary tree node. # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = Noneclass Solution: def increasingBST(self, root: TreeNode) -> TreeNode: if not root: return None nums = [] def midSort(root):# 中序遍历 if not root: return if root.left: midSort(root.left) nums.append(root.val) if root.right: midSort(root.right) midSort(root) node = TreeNode(0)# 新建一个根结点的父结点 cur = node for num in nums:# 构建只有右子结点的树 cur.right = TreeNode(num) cur = cur.right return node.right# 返回根节点

【深度优先遍历|LeetCode —— 897. 递增顺序查找树（Python）】时间复杂度为O(n)，空间复杂度为O(n)。