import java.util.ArrayDeque;
import java.util.Deque;

// 2中解法： 1.中序遍历递归写法 2.非递归写法
public class _230 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Solution1 {
        public int kthSmallest(TreeNode root, int k) {
            int[] p = new int[2];
            inOrder(root, p, k);
            return p[1];
        }

        public void inOrder(TreeNode root, int[] p, int k) {
            if (root == null) return;
            inOrder(root.left, p, k);
            if (p[0] < k) {
                p[0]++;
                p[1] = root.val;
            } else if (p[0] == k) {
                return;
            }
            inOrder(root.right, p, k);
        }
    }

    static class Solution2 {
        public int kthSmallest(TreeNode root, int k) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            int count = 0;
            Integer val = null;
            while (root != null || !stack.isEmpty()) {
                if (root == null || root.left == null) {
                    if (root == null) root = stack.pop();
                    val = root.val;
                    count++;
                    root = root.right;
                    if (count == k) return val;
                    continue;
                }
                stack.push(root);
                root = root.left;

            }
            return val;
        }

    }
}