[230. Kth Smallest Element in a BST] #leetcode

230_0822.java

class Solution {
    private Integer result;
    private Integer count = 0;
        
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return result;
    }
    
    public void dfs(TreeNode node, int k) {
        if (count > k || node == null) return;
        dfs(node.left, k);
        // do sth
        count++;
        if (k == count) result = node.val;
        
        dfs(node.right, k);
    }
}

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