給你一棵二叉搜索樹，請你 按中序遍歷 將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節點成為樹的根節點，并且每個節點沒有左子節點，只有一個右子節點。

示例 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

解題思路

二叉搜索樹中序遍歷的次序就是由小到大的，因此我們在中序遍歷的過程中，可以新建一個頭節點，然后按中序遍歷的順序，將題目中給出的二叉樹節點，一個一個地連在新樹上面。在中序遍歷的時候，修改節點指向就可以實現。具體地，當我們遍歷到一個節點時，把它的左孩子設為空，并將其本身作為上一個遍歷到的節點的右孩子。這里需要有一些想象能力。遞歸遍歷的過程中，由于遞歸函數的調用棧保存了節點的引用。

下面的代碼中，使用了 dummy 節點，它一般在鏈表題中出現。在鏈表題目中，我們為了防止鏈表的頭結點發生變化之后，不好維護頭結點，我們設置 dummy 從而保證頭結點不變。這個題目中設置了 dummy ，從而保證了在新的樹中，dummy 是根節點，不需要在遞歸的時候選擇根節點，最終返回的時候，要返回的是 dummy.right。

代碼

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/var t = new(TreeNode)
func increasingBST(root *TreeNode) *TreeNode {res:=tfindIncreasingBST(root)return res.Right
}
func findIncreasingBST(root *TreeNode)  {if root.Left!=nil{findIncreasingBST(root.Left)}root.Left=nilt.Right=roott=t.Rightif root.Right!=nil{findIncreasingBST(root.Right)}}