欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉搜索树的第k个结点(剑指offer第63题)

程序员文章站 2022-07-10 20:14:42
...

一、题目描述

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

二、解题思路

   思路:搜索二叉树采用中序遍历的结果就是排好序的,我们用list保存下遍历的结果,在找到第k个值。

   改进思路:不用list保存,使用一个变量作为计数器,累加到k值时,返回(递归遍历)

三、java代码

public class Solution_63 {
     /**
      * 给定一棵二叉搜索树,请找出其中的第k小的结点。
      * 例如, (5,3,7,2,4,6,8)    中,按结点数值大小顺序第三小结点的值为4。
      */
	ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
	TreeNode KthNode_1(TreeNode pRoot, int k)
    {
        //搜索二叉树采用中序遍历的结果就是排好序的,我们用list保存下遍历的结果,在找到第k个值。
		if(pRoot == null || k<=0){
			return null;
		}
		inOrder(pRoot);
		TreeNode treeNode = pRoot;
		if(k<=arr.size()){
			treeNode = arr.get(k-1);
		}else {
			return null;
		}
		return treeNode;
    }
	public void inOrder(TreeNode root){  //中序遍历
		if(root == null){
			return;
	     }
		if(root.left != null){
			inOrder(root.left);
		}
		arr.add(root);
		if(root.right != null){
			inOrder(root.right);
		}
	}	
	
	//改进:不用list保存,使用一个变量作为计数器,累加到k值时,返回(递归遍历)
	int index = 0;  //计数器
	TreeNode KthNode_2(TreeNode pRoot, int k){
		if(pRoot != null){
			TreeNode node = KthNode_2(pRoot.left, k);
			if(node != null){
				return node;
			}
			index ++;
			if(index == k){
				return pRoot;
			}
			node = KthNode_2(pRoot.right, k);
			if(node != null){
				return node;
			}
		}
		return null;
	} 
	
	//也是改进版,非递归遍历,用循环
	 int count = 0;    //计数器
	    TreeNode KthNode_3(TreeNode pRoot, int k)
	    {
	        if(count > k || pRoot == null)
	            return null;
	        TreeNode p = pRoot;
	        Stack<TreeNode> LDRStack = new Stack<TreeNode>();
	        TreeNode kthNode = null;
	        while(p != null || !LDRStack.isEmpty()){
	            while(p != null){
	                LDRStack.push(p);
	                p = p.left;
	            }
	            TreeNode node = LDRStack.pop();
	            System.out.print(node.val+",");
	            count++;
	            if(count == k){
	                kthNode = node;
	                break;
	            }
	            p = node.right;
	        }
	        return kthNode;
	    }
}