剑指offer：二叉搜索树的第K个节点

题目描述

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

思路：根据题目的意思，要找到节点的第K小的节点。由于题目本身给出的条件是二叉搜索树，也就是二叉排序树，对它进行中序遍历序列得出的序列便是排序好的已经有序的。创建一个ArrayList，用来存储TreeNode，由此可直接返回排序好的序列，取第K-1个即可。

import java.util.ArrayList;

public class Solution {

    ArrayList<TreeNode> list = new ArrayList<TreeNode>();

    TreeNode KthNode(TreeNode pRoot, int k)

    {

        zhongxu(pRoot);//对给定的序列进行中序遍历

        if(k>=1 && k <= list.size()){//判断k的范围是否满足条件

            return list.get(k-1);

        }

        return null;

    }

    void zhongxu(TreeNode cur){  //中序遍历写法

        if(cur!=null){

            zhongxu(cur.left);

            list.add(cur);

            zhongxu(cur.right);

        }

    }

}