二叉搜索树的第k个结点

 * 题目描述
 * 给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
 * 示例1
 * 输入
 * {5,3,7,2,4,6,8},3
 * 返回值
 * {4}
 * 说明
 * 按结点数值大小顺序第三小结点的值为4

思路:

对于二叉搜索树,由于二叉搜索树具有以下特征:
对于树中每个节点：
若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

我们采用中序遍历二叉搜索树时候,其遍历结果即是从小到大的过程,因此我们可以采用求中序遍历结果求其排序结果,对于这种不需要知道所有排序结果的清空,我们可以用非递归的方法去检索,这样发现了结果即可以提前中止.

代码:

import java.util.Stack;
public class Solution {
   //当前要找的是数字第count小的数据
    int count = 1;

    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k < 1) {
            return null;
        }

        TreeNode res = midSearch(pRoot, k);
        return res;
    }

    //proot不为null
    private TreeNode midSearch(TreeNode pRoot, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || pRoot != null) {
            if (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            } else {
                pRoot = stack.pop();
                if (count == k) {
                    return pRoot;
                } else {
                    pRoot= pRoot.right;
                }
                count++;
            }
        }
        return null;
    }
}

如果想看非递归的各种中序啊左序啊有序啊可以看看
树遍历: https://www.jianshu.com/nb/40413732
二叉树中序非递归版本: https://www.jianshu.com/p/0ef952bf534c