二叉搜索树遍历模板

根据二叉搜索树的性质，左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序，因此我们可以尝试递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 返回二叉树的中序遍历结果
     * @param root TreeNode类 
     * @return ArrayList<Integer> 
     */
    public ArrayList<Integer> minOrder(TreeNode root){
        ArrayList<Integer> result = new ArrayList<>();
        if(root == null)
            return result;
        result.addAll(minOrder(root.left));
        result.add(root.val);
        result.addAll(minOrder(root.right));
        return result;
    }
    
    /**
     * 返回二叉树中第k小的节点值
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    public int KthNode (TreeNode proot, int k) {
        ArrayList<Integer> result = minOrder(proot);
        if(result == null || k <= 0 || k > result.size()) {
            return -1;
        }
        return result.get(k - 1); // 列表索引从0开始，所以需要k-1
    }
}