897. Increasing Order Search Tree

Problem

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:

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

Note:

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

Problem Summary

Given a tree, rearrange the tree according to inorder traversal, so that the leftmost node in the tree is now the root of the tree, and each node has no left child and only one right child.

Notes:

• The number of nodes in the given tree is between 1 and 100.
• Each node has a unique integer value in the range from 0 to 1000.

Solution Ideas

• Given a tree, the requirement is to arrange all children of the tree onto the right subtree.
• According to the problem statement, we can first perform an inorder traversal of the original tree, and then place all nodes on the right subtree in the order of the inorder traversal. See Solution 2.
• The previous solution reconstructs a new tree. Is there a way to directly modify the original tree? This saves storage space. Although modifying original values is usually not recommended in software development, algorithm problems pursue optimal space and time, so it is worth considering. A tree can be regarded as a linked list with multiple children. This problem can be viewed as an operation similar to reversing a linked list. Once this is understood, it becomes easy. First find the leftmost node in the left subtree; this node is the root node of the new tree. Then traverse back in sequence, continuously recording the last node visited previously as tail, and while traversing, link subsequent nodes together. After the final "reversal" is completed, we get the form required by the problem. See Solution 1 for the code implementation.

Code

package leetcode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// Solution 1 Linked list idea
func increasingBST(root *TreeNode) *TreeNode {
	var head = &TreeNode{}
	tail := head
	recBST(root, tail)
	return head.Right
}

func recBST(root, tail *TreeNode) *TreeNode {
	if root == nil {
		return tail
	}
	tail = recBST(root.Left, tail)
	root.Left = nil               // Cut the connection between root and its Left to avoid forming a cycle
	tail.Right, tail = root, root // Attach root to tail, and keep tail pointing to the end
	tail = recBST(root.Right, tail)
	return tail
}

// Solution 2 Simulation
func increasingBST1(root *TreeNode) *TreeNode {
	list := []int{}
	inorder(root, &list)
	if len(list) == 0 {
		return root
	}
	newRoot := &TreeNode{Val: list[0], Left: nil, Right: nil}
	cur := newRoot
	for index := 1; index < len(list); index++ {
		tmp := &TreeNode{Val: list[index], Left: nil, Right: nil}
		cur.Right = tmp
		cur = tmp
	}
	return newRoot
}

func inorder(root *TreeNode, output *[]int) {
	if root != nil {
		inorder(root.Left, output)
		*output = append(*output, root.Val)
		inorder(root.Right, output)
	}
}