LeetCode100之二叉搜索树中第K小的元素(230)–Java

1.问题描述

给定一个二叉搜索树的根节点 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

提示

• 树中的节点数为 n 。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

难度等级

中等

题目链接

[二叉搜索树中第K小的元素]( bst/description/?envType=study-plan-v2&envId=top-100-liked “二叉搜索树中第K小的元素”)

2.解题思路

这道题是要求我们求二叉搜索树中第K小的元素，熟悉树的遍历方式和二叉搜索树概念的读者，应该不难想到，如果我们使用中序遍历来遍历二叉搜索树，那我们将可以得到一个升序的有序序列。 所以这道题要求我们求第K小的元素，其实就是要求中序遍历的有序序列中的第K个元素而已。 理解了题意之后，我们就可以开始来操作了。一般我们的中序遍历使用递归来实现的，今天这里我提供另外一种实现遍历的方法，也就是迭代的方法。 这里，我们首先需要创建一个栈，用来辅助我们的遍历，后面我们会将节点和空节点一起放入栈中，空节点用作标记，只有被空节点标记的节点才会被遍历处理(换句话说，就是我们之处理空节点后的第一个节点)。 //用于辅助遍历 Stack stack = new Stack<>(); 判断根节点是否为空，不为空则将根节点入栈，并定义一个计数遍历用于计数，方便我们找到第K个节点。 //栈不为空，将节点存入栈中 if(root != null){ stack.push(root); } //用于计数遍历了多少节点 int count = 0; 接着，我们就可以用一个while循环开始遍历了，循环的结束条件是栈为空，栈空了自然就没有节点可以处理了。 //开始遍历 while(!stack.isEmpty()) 接下来，是while循环内的单层迭代逻辑。 我们从栈中取出栈顶的节点(node)，判断该节点是否为空。 //从栈中取出一个节点 TreeNode node = stack.pop(); //判断该节点是否为空 if(node != null){ ….. }else{ ….. } 栈顶节点(node)不为空，则不是待处理节点，我们要将它和它的左右节点放入栈中。这里，我们需要根据遍历的方法，确定节点放入栈中的顺序。由于我们是要中序遍历，处理节点的顺序是左根右，再加上栈是后进先出的，所以节点入栈的顺序应该是右根左。我们在存入左右节点时，要先判断左右节点是否为空，为空的话我们则不入栈，防止与空标记冲突混淆；在存入根节点之后，存入一个空节点用于将根节点标记为待处理节点，这样下一次弹出该空节点，就意味着要处理该根节点了。 //非空,继续往栈中放入节点 //中序遍历-> 左 根 右 //存入栈中的循序-> 右 根 左 //右节点 if(node.right != null){ stack.push(node.right); } //存入根节点 stack.push(node); //存入空节点，用做标记 stack.push(null); //左节点 if(node.left != null){ stack.push(node.left); } 如果栈顶节点(node)为空，说明下一个节点是待处理节点。我们将待处理节点从栈顶取出，并让计数变量+1。接着判断计数变量是否等于K，如果等于K，说明我们找到了我们要的节点，直接将当前节点的值返回即可，如果不等于K，接着遍历。 //为空，处理下一个节点 //弹出待处理节点 node = stack.pop(); //计数+1 count++; //判断是否为第K个被处理的节点 if(count == k){ //是，返回结果 return node.val; } 如果遍历结束后，还是找不到第K小的元素，则直接返回-1。 return -1;

3.代码展示

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode() {}
• TreeNode(int val) { this.val = val; }
• TreeNode(int val, TreeNode left, TreeNode right) {
• this.val = val;
• this.left = left;
• this.right = right;
• }
• } */ class Solution { public int kthSmallest(TreeNode root, int k) { //用于辅助遍历 Stack stack = new Stack<>(); //栈不为空，将节点存入栈中 if(root != null){ stack.push(root); } //用于计数遍历了多少节点 int count = 0; //开始遍历 while(!stack.isEmpty()){ //从栈中取出一个节点 TreeNode node = stack.pop(); //判断该节点是否为空 if(node != null){ //非空,继续往栈中放入节点 //中序遍历-> 左 根 右 //存入栈中的循序-> 右 根 左 //右节点 if(node.right != null){ stack.push(node.right); } //存入根节点 stack.push(node); //存入空节点，用做标记 stack.push(null); //左节点 if(node.left != null){ stack.push(node.left); } }else{ //为空，处理下一个节点 //弹出待处理节点 node = stack.pop(); //计数+1 count++; //判断是否为第K个被处理的节点 if(count == k){ //是，返回结果 return node.val; } } } return -1; } }

4.总结

这道题考察的是二叉搜索树的特点和树的遍历方法，我在这里提供了使用迭代方法的中序遍历，这个迭代方法可以看成一个模版，和递归遍历差不多，递归遍历只需要改一下单层递归逻辑中的节点顺序，就可以实现不同方式的遍历，这里的迭代法也只需要改变一下存入栈中节点的顺序，就可以实现不同方式的遍历，注意在遍历时存入根节点的时候要加上一个空节点进行标记。 今天这道题就啰嗦这么多，祝大家刷题愉快~