BST中第K小的元素

66 阅读 0 评论 44 点赞

我是靠谱客的博主霸气猎豹，最近开发中收集的这篇文章主要介绍BST中第K小的元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Leetcode中求二叉搜索树第K小的数，

1. 引入一个变量记录当前节点左子树中节点的个数。

如果频繁操作该树，并且频繁的调用kth函数，可以通过引入一个变量，记录该节点的左子树中节点的个数（其实就是有多少个节点比该节点小），使时间复杂度降低至O(h)（h是树的高度）。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL || k < 1) return NULL;
        int cnt = countNodes(root->left);
        if (k <= cnt)
            return kthSmallest(root->left, k);
        else if (k > cnt + 1)
            return kthSmallest(root->right, k-1-cnt); <span style="font-family: Arial, Helvetica, sans-serif;">//当前节点算一个节点</span>
            
        return root->val;
    }
    //统计当前节点左子树中节点的个数
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

2. 中序遍历

二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。采用迭代形式可以在找到第k小节点时马上退出。

2.1 迭代

需要用栈来做，思路是从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，记录数了几个数了，如果正好是k个，则返回节点值；否则再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右。

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int cnt = 0;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); 
            s.pop();
            ++cnt;
            if (cnt == k) return p->val;
            p = p->right;
        }
        return 0;
    }
};

2.2 递归

递归方法就是对左子结点调用递归函数，判断根节点访问值，右子节点再调用递归函数.

class Solution {
public:
    void DFS(TreeNode *node) {
        if (node == NULL) return;
        if (node->left) DFS(node->left);
        cnt --;
        if (cnt == 0) {
            val = node->val;
            return;
        }
        if (node->right) DFS(node->right);
    }
    int kthSmallest(TreeNode* root, int k) {
       cnt = k;
       DFS(root);
       return val;
    }
private:
    int cnt;
    int val;
};