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

}