剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小于根,右边的元素大于根】
程序员文章站
2022-07-04 23:37:08
1 题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。 2 思路和方法 二叉搜索树【左边的元素小于根,右边的元素大于根】,按照中序遍历的顺序打印出来正好就是排序好的顺序。 中序遍历这颗二叉树,然后设置一个变量,访 ......
1 题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
2 思路和方法
二叉搜索树【左边的元素小于根,右边的元素大于根】,按照中序遍历的顺序打印出来正好就是排序好的顺序。 中序遍历这颗二叉树,然后设置一个变量,访问一个变量的时候就加一,判断这个变量和k是否相等,如果相等,则将当前的这个结点返回即可
3 c++核心代码
1 class solution { 2 public: 3 treenode* kthnode(treenode* proot, int k) { 4 if (k < 0 || proot == nullptr) { 5 return nullptr; 6 } 7 n = k; 8 inorder (proot); 9 return res; 10 } 11 void inorder (treenode* r) { 12 if (r == nullptr || tag) { 13 return; 14 } 15 inorder (r->left); 16 ++n; 17 if (n == n) { 18 res = r; 19 tag = true; 20 return; 21 } 22 inorder (r->right); 23 } 24 25 int n {0}; 26 int n {0}; 27 bool tag {false}; // 找到的标记,提前结束没必要的搜索 28 treenode* res {nullptr}; 29 };
参考资料
https://blog.csdn.net/qq_35976351/article/details/88619952
上一篇: 站在阳台上刚点了一支烟
推荐阅读
-
剑指offer 面试题63 二叉搜索树的第 k 个结点
-
剑指offer面试题63 二叉搜索树的第k个结点
-
剑指offer - 63二叉搜索树的第k个结点
-
[剑指offer]------63 二叉搜索树的第k个结点
-
剑指offer——面试题63:二叉搜索树的第k个结点
-
二叉搜索树的第k个结点(剑指offer第63题)
-
剑指offer--63.二叉搜索树的第k个结点
-
剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小于根,右边的元素大于根】
-
剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元素小于根,右边的元素大于根】
-
剑指Offer-63. 二叉搜索树的第k个结点