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

题目给出的是该二叉树的层序遍历结果。实际如图
图片说明
  可以看到，4是按大小排序时，第3个节点。如果K=3，即4为所求的值。而对应大小排序的就是中序遍历，中序遍历结果是{2,3,4,5,6,7,8}，所以本题核心需要使用到中序遍历。然后对中序遍历的结果中，取第K个元素即可。这里可以使用数字或者集合存储遍历结果，然后取第k个，但是会产生额外的空间复杂度，当然也可以使用一个变量记录遍历的节点数，当遍历到K个节点时即为所求。

写法1：

  使用数组存储，代码看起来非常的清晰。这个代码还有优化空间，因为完成了所有的遍历，事实上可以在遍历到K时，让遍历退出。

import java.util.ArrayList;
public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k) {
        OrderTraversal(pRoot);
        if(k<1 || list.size()<k)
            return null;
        return list.get(k-1);
    }
    // 中序遍历
    public void OrderTraversal(TreeNode node) { 
        if(node != null) {
            OrderTraversal(node.left);
            list.add(node);
            OrderTraversal(node.right);
        }
    }
}
//优化：传入参数K,并在每次遍历前都判断下k是否符合要求。
//    public void OrderTraversal(TreeNode node,int k) { 
//        if(node != null) {
//            if ( list.size() >= k ) //提前退出
//                return ;
//            OrderTraversal(node.left,k);
//            list.add(node);
//           OrderTraversal(node.right,k);
//       }
//    }

写法2：

  使用递归。

public class Solution {
    int index=0;//记录当前遍历的节点数量
    TreeNode KthNode(TreeNode pRoot, int k) {
        TreeNode pNode = null;
        if(pRoot==null || k<=0)//这里就进行了根节点为null的判断
            return pNode;
        pNode = getKthNode(pRoot,k);
        return pNode;
    }

    public TreeNode getKthNode(TreeNode pRoot, int k){
        TreeNode node = null; 
        if(pRoot.left != null)
            node = getKthNode(pRoot.left,k);       
        //pRoot的某个子节点为null时进入下面代码
        index++;
        if(k == index)
            node = pRoot;  //满足条件就将pRoot赋值给node
        //当node赋值时已经找到时，不需要再遍历了，赋值后就不为null，所以要加上这个判断条件
        //写node == null或者k<index都是可以的。
        if(node == null && pRoot.right!=null)
            node = getKthNode(pRoot.right,k);       
        return node;
    }
}

写法3：

  使用栈。

import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        int count = 0;
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>(); 
        TreeNode node = pRoot;
        //中序遍历
        while(!stack.isEmpty() || node != null){ 
            if(node != null){
                stack.push(node); //当前节点不为null，应该寻找左子节点，准备让左子节点入栈
                node = node.left;
            }else{
                node = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。
                count++;//弹出时，才应该计数
                if(count == k){ //相等时就返回
                    return node;
                }
                node = node.right;//左边遍历完，还没到K，就得找右子节点
            }
        }
        return null;
    }
}