# 897. Increasing Order Search Tree 递增顺序搜索树

@TOC

## # 题目描述

Given a 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.

## # 解题方法

### # 重建二叉树

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
array = self.inOrder(root)
if not array:
return None
newRoot = TreeNode(array[0])
curr = newRoot
for i in range(1, len(array)):
curr.right =TreeNode(array[i])
curr = curr.right
return newRoot

def inOrder(self, root):
if not root:
return []
array = []
array.extend(self.inOrder(root.left))
array.append(root.val)
array.extend(self.inOrder(root.right))
return array
``````

### # 数组保存节点

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
res = self.inOrder(root)
if not res:
return
dummy = TreeNode(-1)
cur = dummy
for node in res:
node.left = node.right = None
cur.right = node
cur = cur.right
return dummy.right

def inOrder(self, root):
if not root:
return []
res = []
res.extend(self.inOrder(root.left))
res.append(root)
res.extend(self.inOrder(root.right))
return res
``````

### # 中序遍历时修改指针

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
dummy = TreeNode(-1)
self.prev = dummy
self.inOrder(root)
return dummy.right

def inOrder(self, root):
if not root:
return None
self.inOrder(root.left)
root.left = None
self.prev.right = root
self.prev = self.prev.right
self.inOrder(root.right)
``````