题目描述

题目链接:897. 递增顺序搜索树 - 力扣（LeetCode） (leetcode-cn.com)

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

示例1:

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

示例2:

输入：root = [5,1,7]
输出：[1,null,5,null,7]

• 树中节点数的取值范围是 [1, 100]
• 0 <= Node.val <= 1000

方法一 中序遍历 用list保存记录

• 首先对题目给出的二叉搜索树进行中序遍历，并用list保存
• 然后根据链表，创建一个只含右节点的二叉搜索树

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if(root == null){
            return null;
        }
        inOrder(root, list);
        int len = list.size();
        for(int i = 0; i < len - 1; i++){
            //获取当前节点
            TreeNode cur = list.get(i);
            //获取下一节点
            TreeNode next = list.get(i + 1);
            //当前节点左节点置空
            cur.left = null;
            //当前节点的右节点就是下一节点
            cur.right = next;
        }
        //获取最后一个节点
        TreeNode last = list.get(len - 1);
        //将最后一个节点的左右节点置空
        last.left = null;
        last.right = null; 
        return list.get(0);
    }
    //中序遍历
    void inOrder(TreeNode root, List<TreeNode> list){
        if(root != null){
            inOrder(root.left, list);
            list.add(root);
            inOrder(root.right, list);
        }
    }
}