剑指offer 62.二叉搜索树的第k个结点

剑指offer 62.二叉搜索树的第k个结点

题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路

二叉搜索树的中序遍历是递增的，找到第k小的话，那就只需要中序遍历即可，遍历的第k个数就是所需的数。

代码

public class TreeNode {

  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

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

  }

}

TreeNode KthNode(TreeNode pRoot, int k) {
  if(pRoot == null || k == 0) {
    return null;
  }
  int count = 0;
  Stack<TreeNode> stack = new Stack<>();
  while (pRoot != null || ! stack.isEmpty()) {
    while (pRoot != null) {
      stack.push(pRoot);
      pRoot = pRoot.left;
    }
    pRoot = stack.pop();
    count ++;
    if(count == k) {
      return pRoot;
    }
    pRoot = pRoot.right;
  }
  return null;
}