面试集合剑指offer——二叉搜索树第k个结点

算法小能手

发布日期: 2019-02-10 17:06:45 浏览量: 272
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

题目描述

给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

思路简述

  • 递归的方式:二叉搜索树的中序遍历就是排序的,所以用中序遍历,每一次中间的时候判断是否等于k即可。

  • 非递归的方式:运用栈进行操作。相当于用栈实现了中序遍历,在中间进行了个数的判断。

代码实现

递归

  1. int count = 0;
  2. TreeNode KthNode(TreeNode pRoot, int k)
  3. {
  4. if(pRoot != null) {
  5. TreeNode leftNode = KthNode(pRoot.left, k);
  6. if(leftNode != null)
  7. return leftNode;
  8. count++;
  9. if(count == k)
  10. return pRoot;
  11. TreeNode rightNode = KthNode(pRoot.right, k);
  12. if(rightNode != null)
  13. return rightNode;
  14. }
  15. return null;
  16. }

  1. TreeNode KthNode(TreeNode pRoot, int k)
  2. {
  3. Stack<TreeNode> stack = new Stack<TreeNode>();
  4. if(pRoot==null||k==0) return null;
  5. int t=0;
  6. while(pRoot!=null ||stack.size()>0){
  7. while(pRoot!=null){
  8. stack.push(pRoot);
  9. pRoot = pRoot.left;
  10. }
  11. if(stack.size()>0){
  12. pRoot= stack.pop();
  13. t++;
  14. if(t==k) return pRoot;
  15. pRoot= pRoot.right;
  16. }
  17. }
  18. return null;
  19. }
上传的附件

发送私信

16
文章数
4
评论数
最近文章
eject