230-二叉搜索树中第K小的元素

LeetCode

发布日期: 2022-02-22

LeetCode 230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

method 1

算当前节点的左节点有leftNum个，当前节点是第leftNum+1小节点，如果

如果leftNum+1==k，当前节点就是第k小节点，直接返回
如果leftNum+1>k，说明第k小的节点还在左边，继续往左边找
如果leftNum+1<k，说明第k小节点在右边，需要找右边的第k-leftNum-1小节点

int traversal(TreeNode *root) {
    if (!root) return 0;
    return 1 + traversal(root->left) + traversal(root->right);
}
int kthSmallest(TreeNode* root, int k) {
    int leftNum = traversal(root->left);
    if (leftNum == k - 1) return root->val;
    else if (leftNum > k - 1) return kthSmallest(root->left, k);
    return kthSmallest(root->right, k - leftNum - 1);
}

假设要找第4小的节点，

如果leftNum=3，说明该节点左边有3个元素，该节点就是第4小的节点
如果leftNum=5，说明第4小的节点还在左边，往左边找第4小的节点
如果leftNum=2，说明该节点是第3小的节点，第4小的节点在它的右边第一个，如果应该往右边找第1小的节点，这个1是通过4-leftNum-1算出来的

时间复杂度：$\mathcal{O}(h \cdot 2^h)$，最差情况下是找第1小的数，并且是满二叉树，高度为$h$，所以要找$h$次，每次找左子树节点都要遍历一次左子树，分别是$2^{h-1},2^{h-2},\ldots,2^0$，加起来是$2^h-1$，所以时间复杂度是$\mathcal{O}(h \cdot 2^h)$
空间复杂度：$\mathcal{O}(h^2)$，递归的栈空间，分别是$h-1,h-2,\ldots,0$，加起来是$\frac{h(h-1)}{2}$

method 2

按照中序遍历从最左边的元素开始找

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        if (--k == 0) break;
        root = root->right; 
    }
    return root->val;
}