Kth Smallest Element in a BST leetcode

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

非递归方法: 类似线序遍历, 每访问到一个最小的count++, 直到count == k

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        int count = 0;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                count++;
                
                if (count == k) {
                    return tem.val;
                }
                node = tem.right;
            }
        }
        return 0;
    }
}

递归方法:

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = count(root.left);
        if (count + 1 > k) {
            return kthSmallest(root.left, k);
        } else if (count + 1 < k) {
            return kthSmallest(root.right, k - count- 1);
        } else {
            return root.val;
        }
    }
    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
}