897. 递增顺序搜索树

给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：
输入：root = [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

示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]
�
二叉搜索树的中序遍历结果是一个升序的有序序列
遍历有序序列，构建一个只有右子节点的树

public TreeNode increasingBST(TreeNode root) {
    List<Integer> valList = new ArrayList<>();
    inOrder(root,valList);
    // 中序遍历结果第一个元素作为新的树的根节点
    TreeNode newRoot = new TreeNode(valList.get(0));
    // 借用一个临时节点对象作为下一个节点的父节点
    TreeNode preNode = newRoot;
    for (int i = 1; i < valList.size(); i++) {
        // 创建一个新节点
        TreeNode node = new TreeNode(valList.get(i));
        // 将当前节点设置为上一个节点的右子节点
        preNode.right = node;
        // 将当前节点设置为下一个节点的父节点
        preNode = node;
    }
    return newRoot;
}
/**
 * 二叉搜索树的中序遍历结果是个有序数组
 *
 * @param node
 * @param valList
 */
private void inOrder(TreeNode node, List<Integer> valList) {
    if (node == null) {
        return;
    }
    inOrder(node.left, valList);
    valList.add(node.val);
    inOrder(node.right, valList);
}