递归/树的遍历/ BST 中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

Clarification:
这是一棵二叉搜索树，因此它的中序遍历会是一个从小到大排列的有序数组。

Possible Solution

1. 递归
2. 迭代

Coding

 ArrayList<Integer> result = new ArrayList<>();
    public int kthSmallest1(TreeNode root, int k) {
        helper(root);
        return result.get(k-1);
    }

    private void helper(TreeNode root){
        if(root!=null){
            helper(root.left);
            result.add(root.val);
            helper(root.right);
        }
    }

这个代码，是我仿照陈皓大神的Python版本写的。写算法题练习一定要看高手写的代码，可以稳定关注几位高手。网上查的代码实在是逻辑凌乱。

helper方法实现的是对BST的中序遍历。使用的是递归的方法。所谓递归，就是自己调用自己。递归是有模板的，通常把递归的退出条件放在开头，接着是处理和扩散，最后是退出前的处理。而此处处理就是result.add(root.val)语句，把某节点添加到result数组中，就是代表已访问了某个节点。

倘若把helper方法的三句语句颠倒顺序，就成了其他的遍历方式，比如前序、或者后序。递归是一种计算机的思维方式，而不是我们人脑的天然方式。因此想要理解递归总是需要花费一些功夫。就树的遍历而言，假如把“helper(root.left);”放在第一句，那么就会首先优先遍历左子树，一直到最左边的节点，然后遇到递归的返回条件，向下的操作结束，开始进行结果的返回。

递归是个层层深入的结构，从最底层返回到倒数第二层，执行倒数第二层的“result.add(root.val);”操作，然后再执行helper(root.right);操作。右边的子树与左边的子树进行类似的操作。这其实是一个分形的状态，进入到树的下一层，与上一层是相似的形态。

再看下非递归的形式。在递归操作中，栈是由系统自动为你分配的，而在非递归的代码中，需要你自己创建一个堆栈，并管理节点的入栈和出栈操作。

 Stack<TreeNode> s = new Stack<>();
    public int kthSmallest(TreeNode root, int k){
        //整个大循环的退出条件是栈为空，并且root为空。
        //两者有一个不为空，循环都会继续进行下去，直到k==0为止。
        while(s!=null || root!=null){
            //这段代码的功能是：从根节点出发，往左子树走，
            //一直走到最底层的左节点，并把沿途遇到的左节点统统入栈。
            while(root!=null){
                s.push(root);
                root = root.left;
            }
            //然后开始出栈，每出栈一个节点，就代表排除了一个剩余数组中的最小值，即离目标k又近了一步。
            root = s.pop();
            k -= 1;
            //设定退出条件，需要注意代码中把减一的操作放在检验之前。
            //然后开始遍历当前节点的右孩子。
            if(k==0) return root.val;
            root = root.right;
        }
        return 0;