leetcode_897

题目来源：https://leetcode.com/problems/increasing-order-search-tree/

思路： ① 中序遍历，得到有序数组
② 重新构建树，新建一个节点ans=TreeNode（0），令cur=ans，cur此时是一个游标，遍历上一步得到的中序遍历数组，cur.right = new TreeNode(),cur = cur.right。最后返回ans.right,因为这个树的根节点不是之前树的值（排除）。

代码：

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }

• }
  */
  class Solution {
  public TreeNode increasingBST(TreeNode root) {

  return increasingBST(root, null);
  

  }

  public TreeNode increasingBST(TreeNode root, TreeNode tail) {

  if (root == null) return tail;
  TreeNode res = increasingBST(root.left, root);
  root.left = null;
  root.right = increasingBST(root.right, tail);
  return res;
  

  }
  }