二叉搜索树的第k个结点

题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

分析
二叉搜索树的一个特点就是二叉搜索树的中序遍历得到的序列是递增有序的，那么想要获得节点数值大小顺序第几，可以通过中序遍历得到的序列获得。

方法一
采用ArrayList保存获得的序列

	TreeNode KthNode(TreeNode pRoot, int k) {
		
		if(pRoot == null || k <= 0) {
			return null;
		}
		ArrayList<TreeNode> list = new ArrayList<TreeNode>();
		MiddleList(pRoot, list);
		
		if(k > list.size()) {
			return null;
		}
		return list.get(k - 1);
		
	}
	
	public void MiddleList(TreeNode node, ArrayList<TreeNode> list) {
		if(node != null) {
			MiddleList(node.left, list);
			list.add(node);
			MiddleList(node.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;
		
		
	}