[leetcode] 897. Increasing Order Search Tree

Description

Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:

Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9

Constraints:

The number of nodes in the given tree will be between 1 and 100.Each node will have a unique integer value from 0 to 1000.

分析

题目的意思是：给定一个二叉排序树，然后变成一个只有右结点的二叉排序树。最简单的做法就是二叉树的中序遍历以后再构造一个只有右结点的二叉排序树就行了。还有另一种递归的解法，我比较欣赏，利用一个空结点cur来指向根结点，然后进行中序遍历，对于左子树，先递归，然后cur的右结点指向左子树，然后cur指向当前节点，再遍历右结点。比较抽象。最后返回该空结点的右节点就是结果了。

代码

# 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 inorder(self,node): if(node is None): return self.inorder(node.left) node.left=None self.cur.right=node self.cur=node self.inorder(node.right) def increasingBST(self, root: TreeNode) -> TreeNode: ans=self.cur=TreeNode(None) self.inorder(root) return ans.right

参考文献

[LeetCode] solution