题目大意：
递增顺序查找树
给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例 ：
输入: [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 范围内的唯一整数值。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=897
解题思路分析：
本题给出的树实际上是一颗二分查找树BST，按照中序遍历即可将所有节点按照升序顺序遍历出来。遍历出所有节点之后，我们再使用递归将所有节点构建成题目要求的形式即可。
实现代码：
public TreeNode increasingBST(TreeNode root) {
// 中序遍历所有节点
help(root);
// 构建题目要求的树
return makeTree(0);
}
List<Integer> list = new ArrayList<>();
// 标准的中序遍历
void help(TreeNode root){
if(root.left!=null) help(root.left);
list.add(root.val);
if(root.right!=null) help(root.right);
}
// 构建题目要求的树
TreeNode makeTree(int index){
if(index==list.size()) return null;
TreeNode node = new TreeNode(list.get(index));
node.right=makeTree(index+1);
return node;
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 52.07% of Java online submissions for Increasing Order Search Tree.
Memory Usage: 41.7 MB, less than 46.88% of Java online submissions for Increasing Order Search Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-897-increasing-order-search-tree-解题思路分析/