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
}
Last modified 6mo ago