题目描述

给定一棵二叉搜索树（对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。），请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
思想：通过中序遍历，把值存入list中，然后取出第k-1个。

  1. import java.util.ArrayList;
  3. public class Solution {
  4.     ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
  5.     TreeNode KthNode(TreeNode pRoot, int k)
  6.     {
  7.         middleOrder(pRoot); 
  8.         if(arr.size()<1||k<1||k>arr.size()) {
  9.             return null;
  10.         }
  11.         return arr.get(k-1);
  12.     }
  13.     public void middleOrder(TreeNode pRoot) {
  14.         if(pRoot!=null) {
  15.             middleOrder(pRoot.left);
  16.             arr.add(pRoot);
  17.             middleOrder(pRoot.right);
  18.         }
  19.     }