寻找查找二叉树的第K小节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M

解题思路:由于是二叉搜索树（二叉查找树），故中序遍历该树，得到的是有序的。所以在遍历的过程中返回第K个节点就可以了。

采用非递归中序遍历：

import java.util.Stack;
public class Solution {
   
    TreeNode KthNode(TreeNode pRoot, int k) {
      if(k==0||pRoot==null) return null;
      else
      {
        int count=0;
        Stack<TreeNode> s=new Stack<TreeNode>();
        TreeNode node=pRoot;
        
        while(!s.empty()||node!=null)
        {
          if(node!=null)
          {
            s.push(node);
            node=node.left;  //遍历左子树；
          }
          else
          {
            node=s.pop();
            count++;
            if(count==k) return node;
            node=node.right;    //遍历右子树
          }
        }
        return null;
        
      }
       
    }
 

}