# 897.increasing order search tree

**897 Increasing Order Search Tree**

> 给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

```
示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \
1        7   9

输出：[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


提示：
给定树中的结点数介于 1 和 100 之间。
每个结点都有一个从 0 到 1000 范围内的唯一整数值。
```

方法：最直观的方法是创建一个向量按顺序保存每个节点，最后再从向量索引0开始，对每个借电左子树清空，右子树链接到下一个节点。但是会显示超时。如下:

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
vector<TreeNode*> st;
void init_st(TreeNode* root)
{
if(root != NULL)
        {
            init_st(root->left);
            st.push_back(root);
            init_st(root->right);

        }

}
public:
    TreeNode* increasingBST(TreeNode* root) {
        init_st(root);
        for(int i=0;i<st.size()-1;i++)
        {
            st[i]->left =NULL;
            st[i]->right=st[i+1];
        }
        return st[0];


    }
};
```

因为排序占用了比较多的时间，而且开辟一个空间来存储所有的节点，最后还要遍历一遍，并对每个节点修改。最后测试超时。 另一个方法是：

* 采用中序遍历，先计算root左子树部分，新建一个TreeNode，每次递归调用时，将新建树list的右子连接到新建节点，然后list右移，计算root右子树部分。

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
 public:
    void midTraverse(TreeNode* root, TreeNode* &list)
{
	if (!root) return;
	midTraverse(root->left, list);
	TreeNode *newNode = new TreeNode(root->val);
	list->right = newNode;
	list = list->right;
	midTraverse(root->right, list);
}
TreeNode* increasingBST(TreeNode* root)
{
	TreeNode* newTree = new TreeNode(0);
	TreeNode* res = newTree;
	midTraverse(root, newTree);
	return res->right;
}
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/897.increasing_order_search_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.