剑指offer——二叉搜索树的第k个节点

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

解题思路：

这其实是二叉搜索树的中序遍历。

 1 /*
 2 public class TreeNode {
 3     int val = 0;
 4     TreeNode left = null;
 5     TreeNode right = null;
 6 
 7     public TreeNode(int val) {
 8         this.val = val;
 9 
10     }
11 
12 }
13 */
14 import java.util.Stack;
15 public class Solution {
16     TreeNode KthNode(TreeNode pRoot, int k)
17     {
18         Stack<TreeNode> stack = new Stack<>();
19         int count=0;
20         if (pRoot==null)
21             return null;
22         TreeNode node = pRoot;
23         while(node!=null || !stack.isEmpty())
24         {
25             if(node!=null)
26             {
27                 stack.push(node);
28                 node = node.left;
29             }
30             else
31             {
32                 node = stack.pop();
33                 count++;
34                 if(count==k)
35                 {
36                     return node;
37                 }
38                 node =node.right;
39             }
40         }
41         return null;
42         
43     }
44 
45 
46 }