897. Increasing Order Search Tree

Easy
Given the root of 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 one right child.
Example 1:
​
​
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output:
[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
Example 2:
​
​
Input: root = [5,1,7]
Output:
[1,null,5,null,7]
Constraints:
  • The number of nodes in the given tree will be in the range [1, 100].
  • 0 <= Node.val <= 1000

解題

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func increasingBST(root *TreeNode) *TreeNode {
nodes := make([]int, 0)
​
var helper func(*TreeNode)
helper = func(root *TreeNode){
if root == nil {
return
}
​
if root.Left != nil {
helper(root.Left)
}
​
nodes = append(nodes, root.Val)
​
if root.Right != nil {
helper(root.Right)
}
}
​
helper(root)
​
res := root
for _, n := range nodes {
root.Left = nil
root.Right = &TreeNode{ Val:n }
root = root.Right
}
​
return res.Right
​
}
​
​