#yyds幹貨盤點# leetcode算法題：二叉搜尋樹中第K小的元素

題目：

給定一個二叉搜尋樹的根節點 root ，和一個整數 k ，請你設計一個算法查找其中第 k 個最小元素（從 1 開始計數）。

示例 1：

輸入：root = [3,1,4,null,2], k = 1

輸出：1

示例 2：

輸入：root = [5,3,6,2,4,null,null,1], k = 3

輸出：3

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // 中序周遊生成數值清單
        List<Integer> inorderList = new ArrayList<Integer>();
        inorder(root, inorderList);

        // 構造平衡二叉搜尋樹
        AVL avl = new AVL(inorderList);

        // 模拟1000次插入和删除操作
        int[] randomNums = new int[1000];
        Random random = new Random();
        for (int i = 0; i < 1000; ++i) {
            randomNums[i] = random.nextInt(10001);
            avl.insert(randomNums[i]);
        }
        shuffle(randomNums); // 清單亂序
        for (int i = 0; i < 1000; ++i) {
            avl.delete(randomNums[i]);
        }

        return avl.kthSmallest(k);
    }

    private void inorder(TreeNode node, List<Integer> inorderList) {
        if (node.left != null) {
            inorder(node.left, inorderList);
        }
        inorderList.add(node.val);
        if (node.right != null) {
            inorder(node.right, inorderList);
        }
    }

    private void shuffle(int[] arr) {
        Random random = new Random();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int randIndex = random.nextInt(length);
            int temp = arr[i];
            arr[i] = arr[randIndex];
            arr[randIndex] = temp;
        }
    }
}

// 平衡二叉搜尋樹（AVL樹）：允許重複值
class AVL {
    Node root;

    // 平衡二叉搜尋樹結點
    class Node {
        int val;
        Node parent;
        Node left;
        Node right;
        int size;
        int height;

        public Node(int val) {
            this(val, null);
        }

        public Node(int val, Node parent) {
            this(val, parent, null, null);
        }

        public Node(int val, Node parent, Node left, Node right) {
            this.val = val;
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.height = 0; // 結點高度：以node為根節點的子樹的高度（高度定義：葉結點的高度是0）
            this.size = 1; // 結點元素數：以node為根節點的子樹的節點總數
        }
    }

    public AVL(List<Integer> vals) {
        if (vals != null) {
            this.root = build(vals, 0, vals.size() - 1, null);
        }
    }

    // 根據vals[l:r]構造平衡二叉搜尋樹 -> 傳回根結點
    private Node build(List<Integer> vals, int l, int r, Node parent) {
        int m = (l + r) >> 1;
        Node node = new Node(vals.get(m), parent);
        if (l <= m - 1) {
            node.left = build(vals, l, m - 1, node);
        }
        if (m + 1 <= r) {
            node.right = build(vals, m + 1, r, node);
        }
        recompute(node);
        return node;
    }

    // 傳回二叉搜尋樹中第k小的元素
    public int kthSmallest(int k) {
        Node node = root;
        while (node != null) {
            int left = getSize(node.left);
            if (left < k - 1) {
                node = node.right;
                k -= left + 1;
            } else if (left == k - 1) {
                break;
            } else {
                node = node.left;
            }
        }
        return node.val;
    }

    public void insert(int v) {
        if (root == null) {
            root = new Node(v);
        } else {
            // 計算新結點的添加位置
            Node node = subtreeSearch(root, v);
            boolean isAddLeft = v <= node.val; // 是否将新結點添加到node的左子結點
            if (node.val == v) { // 如果值為v的結點已存在
                if (node.left != null) { // 值為v的結點存在左子結點，則添加到其左子樹的最右側
                    node = subtreeLast(node.left);
                    isAddLeft = false;
                } else { // 值為v的結點不存在左子結點，則添加到其左子結點
                    isAddLeft = true;
                }
            }

            // 添加新結點
            Node leaf = new Node(v, node);
            if (isAddLeft) {
                node.left = leaf;
            } else {
                node.right = leaf;
            }

            rebalance(leaf);
        }
    }

    // 删除值為v的結點 -> 傳回是否成功删除結點
    public boolean delete(int v) {
        if (root == null) {
            return false;
        }

        Node node = subtreeSearch(root, v);
        if (node.val != v) { // 沒有找到需要删除的結點
            return false;
        }

        // 處理目前結點既有左子樹也有右子樹的情況
        // 若左子樹比右子樹高度低，則将目前結點替換為右子樹最左側的結點，并移除右子樹最左側的結點
        // 若右子樹比左子樹高度低，則将目前結點替換為左子樹最右側的結點，并移除左子樹最右側的結點
        if (node.left != null && node.right != null) {
            Node replacement = null;
            if (node.left.height <= node.right.height) {
                replacement = subtreeFirst(node.right);
            } else {
                replacement = subtreeLast(node.left);
            }
            node.val = replacement.val;
            node = replacement;
        }

        Node parent = node.parent;
        delete(node);
        rebalance(parent);
        return true;
    }

    // 删除結點p并用它的子結點代替它，結點p至多隻能有1個子結點
    private void delete(Node node) {
        if (node.left != null && node.right != null) {
            return;
            // throw new Exception("Node has two children");
        }
        Node child = node.left != null ? node.left : node.right;
        if (child != null) {
            child.parent = node.parent;
        }
        if (node == root) {
            root = child;
        } else {
            Node parent = node.parent;
            if (node == parent.left) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
        node.parent = node;
    }

    // 在以node為根結點的子樹中搜尋值為v的結點，如果沒有值為v的結點，則傳回值為v的結點應該在的位置的父結點
    private Node subtreeSearch(Node node, int v) {
        if (node.val < v && node.right != null) {
            return subtreeSearch(node.right, v);
        } else if (node.val > v && node.left != null) {
            return subtreeSearch(node.left, v);
        } else {
            return node;
        }
    }

    // 重新計算node結點的高度和元素數
    private void recompute(Node node) {
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        node.size = 1 + getSize(node.left) + getSize(node.right);
    }

    // 從node結點開始（含node結點）逐個向上重新平衡二叉樹，并更新結點高度和元素數
    private void rebalance(Node node) {
        while (node != null) {
            int oldHeight = node.height, oldSize = node.size;
            if (!isBalanced(node)) {
                node = restructure(tallGrandchild(node));
                recompute(node.left);
                recompute(node.right);
            }
            recompute(node);
            if (node.height == oldHeight && node.size == oldSize) {
                node = null; // 如果結點高度和元素數都沒有變化則不需要再繼續向上調整
            } else {
                node = node.parent;
            }
        }
    }

    // 判斷node結點是否平衡
    private boolean isBalanced(Node node) {
        return Math.abs(getHeight(node.left) - getHeight(node.right)) <= 1;
    }

    // 擷取node結點更高的子樹
    private Node tallChild(Node node) {
        if (getHeight(node.left) > getHeight(node.right)) {
            return node.left;
        } else {
            return node.right;
        }
    }

    // 擷取node結點更高的子樹中的更高的子樹
    private Node tallGrandchild(Node node) {
        Node child = tallChild(node);
        return tallChild(child);
    }

    // 重新連接配接父結點和子結點（子結點允許為空）
    private static void relink(Node parent, Node child, boolean isLeft) {
        if (isLeft) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        if (child != null) {
            child.parent = parent;
        }
    }

    // 旋轉操作
    private void rotate(Node node) {
        Node parent = node.parent;
        Node grandparent = parent.parent;
        if (grandparent == null) {
            root = node;
            node.parent = null;
        } else {
            relink(grandparent, node, parent == grandparent.left);
        }

        if (node == parent.left) {
            relink(parent, node.right, true);
            relink(node, parent, false);
        } else {
            relink(parent, node.left, false);
            relink(node, parent, true);
        }
    }

    // trinode操作
    private Node restructure(Node node) {
        Node parent = node.parent;
        Node grandparent = parent.parent;

        if ((node == parent.right) == (parent == grandparent.right)) { // 處理需要一次旋轉的情況
            rotate(parent);
            return parent;
        } else { // 處理需要兩次旋轉的情況：第1次旋轉後即成為需要一次旋轉的情況
            rotate(node);
            rotate(node);
            return node;
        }
    }

    // 傳回以node為根結點的子樹的第1個元素
    private static Node subtreeFirst(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // 傳回以node為根結點的子樹的最後1個元素
    private static Node subtreeLast(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // 擷取以node為根結點的子樹的高度
    private static int getHeight(Node node) {
        return node != null ? node.height : 0;
    }

    // 擷取以node為根結點的子樹的結點數
    private static int getSize(Node node) {
        return node != null ? node.size : 0;
    }
}