> For the complete documentation index, see [llms.txt](https://dfine.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dfine.gitbook.io/leetcode/897.increasing_order_search_tree.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.