题解 | #二叉搜索树的第k个节点# [P2-T0]

in-order traversal

时间: O(h)
空间: O(h)

import java.util.*;

public class Solution {
  int visited = 0;
  int ans = -1;
  
  public int KthNode (TreeNode proot, int k) {
    recurse(proot, k);
    return ans;
  }
  
  void recurse(TreeNode n, int k) {
    if (n == null) return;
    if (ans != -1) return; // already found kth 
    
    recurse(n.left, k);
    
    visited++;
    if (visited == k) {
      ans = n.val;
    }

    recurse(n.right, k);
  }
}