题解 | #二叉搜索树的第k个节点#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param proot TreeNode类 
 * @param k int整型 
 * @return int整型
 */
int KthNode(struct TreeNode *proot, int k)
{
  int ret = -1;
  //带有栈辅助的中序遍历
  struct TreeNode *stack[1001];
  struct TreeNode *p;
  int count = 0;
  int top = -1;
  p = proot;
  if (!p)
    return -1;
    //会有栈空但是没有遍历完毕,此时可能会有右子树等待并入
    //也有指向NULL但是栈不空等待出栈,那就是常规的出栈操作,出的是左节点
    //所以用栈空并且指针指向NULL作为结束标志
  while (top != -1 || p != NULL)
  {
    //所有左节点入栈
    while (p)
    {
      stack[++top] = p;
      p = p->left;
    }
    //左节点和中间节点出栈,指向右子树准备并入
    if (top != -1)
    {
      count++;
      p = stack[top--];
      if (count == k)
      {
        ret = p->val;
        break;
      }
      p = p->right;
    }
  }
  return ret;
}