【LeetCode-中等题】230. 二叉搜索树中第K小的元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】230. 二叉搜索树中第K小的元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】230. 二叉搜索树中第K小的元素,力扣,# 中等题,leetcode,链表,算法

该题最大的特点就是这个树是二叉树：
【LeetCode-中等题】230. 二叉搜索树中第K小的元素,力扣,# 中等题,leetcode,链表,算法

所以，中序遍历对二叉树的遍历本身就是有序的

方法一：层序遍历 + 集合排序

思想很简单，就是通过层序遍历将节点都加到List集合中，然后调用 Collections.sort(list)排序后，找第k小的数list.get(k-1)

    public int kthSmallest(TreeNode root, int k) {
            List<Integer> list = levelOrder(root);
            Collections.sort(list);
            return list.get(k-1);
            
        }
        public List<Integer> levelOrder(TreeNode root) {
                List<Integer> result = new ArrayList<>();
                Queue<TreeNode> queue = new LinkedList<TreeNode>();
                if(root == null) return result;
                queue.offer(root);
                while(!queue.isEmpty()){
                    int count = queue.size();
                    for(int i =0 ;i< count ;i++){
                      TreeNode node =   queue.poll();
                        result.add(node.val); 
                        if(node.left != null)  queue.offer(node.left);
                         if(node.right != null) queue.offer(node.right);
                    }
                }
                return result;
    }

方法二：中序遍历（栈或者递归）

二叉树中序遍历得到的值序列是递增有序的 借助一个list集合来接收有序的节点然后再按照k去list集合区第k小的数

  List<Integer> list =new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
      
        // dfs(root);    //递归中序
        stackTree(root); //  栈中序
        return list.get(k-1);
        
    }
    //递归中序
    //  public void dfs(TreeNode root) {
    //      if(root == null ) return ;

    //      dfs(root.left);
    //      list.add(root.val);
    //      dfs(root.right);
    //  }

    //  栈中序
     public void stackTree(TreeNode root) {
           Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
           while(!stack.isEmpty() || root != null){
                while(root != null){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                list.add(root.val);
                root = root.right;
           }
     }

方法三（方法二改进）：中序遍历（栈）

二叉树中序遍历得到的值序列是递增有序的那只要栈每次弹出一个元素时就让k-1（直到k=0）例如要第1小的数那么其实就是中序遍历栈弹出的第一个元素（k= k-1 ===0，立马返回第一次pop的数）文章来源地址https://www.toymoban.com/news/detail-683307.html

    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            
            root = stack.pop();
            k--;//每弹出一个元素，就让k--
            if(k == 0) return root.val;//直到k减到0  说明该root.val就是第k小的数
            root = root.right;
        }
        return -1;
     }