09二叉搜索树中第k小的元素

二叉搜索树中第k小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

• 树中的节点数为 n 。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

public 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;
  }
}

int visited = 0;
int res = -1;
boolean find = false;

public int kthSmallest(TreeNode node, int k) {
  if (node == null || find) {
    return res;
  }

  kthSmallest(node.left, k);
  visited++;
  if (visited == k) {
    res = node.val;
    find = true;
  }
  kthSmallest(node.right, k);
  return res;
}

public int kthSmallest(TreeNode root, int k) {
  Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  while (root != null || !stack.isEmpty()) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    --k;
    if (k == 0) {
      break;
    }
    root = root.right;
  }
  return root.val;
}