LeetCode

二叉搜索树的中序遍历就是一个有序的序列

1. 先将二叉搜索树中序遍历得到有序的序列存入数组中

	// 中序遍历二叉树
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }

2. 在数组中删除对应的元素list.remove((Integer) key)
3. 根据删除后的数组构建一颗二叉搜索树

	// 根据有序数组构建二叉搜索树
    public TreeNode buildTree(int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildTree(start, mid - 1);
        root.right = buildTree(mid + 1, end);
        return root;
    }

class Solution {
    List list = new ArrayList<>();
    public TreeNode deleteNode(TreeNode root, int key) {
        // 先遍历得到序列
        inorder(root);
        // 删除对应元素
        list.remove((Integer) key);
        // 重新构成一颗二叉搜索树
        return buildTree(0, list.size() - 1);
    }

    // 根据有序数组构建二叉搜索树
    public TreeNode buildTree(int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildTree(start, mid - 1);
        root.right = buildTree(mid + 1, end);
        return root;
    }

    // 中序遍历二叉树
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head);
    }

    public TreeNode buildTree(ListNode head) {
        if (head == null) return null;
        else if (head.next == null) return new TreeNode(head.val);

        // 根基快慢指针找到链表中点
        ListNode slow = head; // 存储链表中点
        ListNode fast = head;
        ListNode pre = null; // 存储链表中点的前一个节点， 用来移除中点
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        pre.next = null;  // 去除中点

        TreeNode root = new TreeNode(slow.val);
        root.left = buildTree(head);
        root.right = buildTree(slow.next);

        return root;
    }
}