寻找二叉搜索树的第K小的节点

60 阅读 0 评论 40 点赞

我是靠谱客的博主细腻刺猬，最近开发中收集的这篇文章主要介绍寻找二叉搜索树的第K小的节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目要求：

230. Kth Smallest Element in a BST

My Submissions

Total Accepted: 58991
Total Submissions: 148753
Difficulty: Medium

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

Try to utilize the property of a BST.
What if you could modify the BST node's structure?
The optimal runtime complexity is O(height of BST).

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

三种解法：

public int kthSmallest(TreeNode root, int k) {
        int count=countNodes(root.left)+1;
        if(k==count) return root.val;
        if(k<count) return kthSmallest(root.left,k);
        else{
            return kthSmallest(root.right,k-count);
        }
    }
    public int countNodes(TreeNode root){
        if(root==null) return 0;
        return 1+countNodes(root.left)+countNodes(root.right);
    }

以上解法最漂亮，用到了二叉树的结构特性与题目要求

private static int number = 0;
    private static int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        helper(root);
        return number;
    }
    
    public void helper(TreeNode n) {
        if (n.left != null) helper(n.left);
        count--;
        if (count == 0) {
            number = n.val;
            return;
        }
        if (n.right != null) helper(n.right);
    }

上面的解法就是中序遍历的解法，count 与 number 都应设置喂全局变量

public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> st = new Stack<>();
        
        while (root != null) {
            st.push(root);
            root = root.left;
        }
            
        while (k != 0) {
            TreeNode n = st.pop();
            k--;
            if (k == 0) return n.val;
            TreeNode right = n.right;
            while (right != null) {
                st.push(right);
                right = right.left;
            }
        }
        
        return -1; // never hit if k is valid
  }

第三种解法应用了一个栈，与使用队列的效果是一样的，但是在可理解性上不如应用队列。