IT评测·应用市场-qidao123.com

标题: 二叉树的深度搜索专题一＞二叉搜索树中第 K 小的元素 [打印本页]

---

作者: 祗疼妳一个    时间: 2024-12-8 04:04
标题: 二叉树的深度搜索专题一＞二叉搜索树中第 K 小的元素
题目： 
  

 
  

---

  剖析： 
  采用中序遍历+两个全局变量 +剪枝
  两个全局变量：count计数，ret返回，搜索二叉树中由于中序遍历是有序的，把K赋值给count，当count==0时就找到第K小的值，就返回ret 
  

---

  代码： 

1. class Solution {
2.     private int count;
3.     private int ret;
5.     public int kthSmallest(TreeNode root, int k) {
6.         count = k;
7.         dfs(root);
8.         return ret;
9.     }
11.     private void dfs(TreeNode root){
12.         /**中序遍历+两个全局变量+剪枝
13.          */
15.         //剪枝
16.         if(root == null || count == 0) return;
17.         dfs(root.left);
18.         count--;
19.         if(count == 0) ret = root.val;
21.         //剪枝
22.         if(count == 0) return;
23.         dfs(root.right);
24.     }
25. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4