【剑指offer-62】二叉搜索树的第k个结点

• 考点：栈 树
• 时间限制：1秒
• 空间限制：32768K
• 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

---

思路：

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
所以，按照中序遍历顺序找到第k个结点就是结果。

代码：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        TreeNode root = pRoot;
        
        if (root == null || k == 0) {
            return null;
        }
        
        int count = 0; // 计数器
        Stack<TreeNode> stack = new Stack();
        while (root != null || !stack.empty()) {
            // 走到最左边的节点
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            count++;
            if (count == k) {
                return root;
            }
            root = root.right;
        }
        return null;

    }

}

我的问题：

1. 先一直走走到最左边的子树开始遍历，然后把节点pop出来，就是遍历到根节点了。index++。看看现在这个index是不是等于k了，如果是就直接返回root，如果不是，遍历右边子树。

---

其他思路1：

非递归做法

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot == null) {
            return null;
        }
        
        TreeNode l = KthNode(pRoot.left, k);
        if (l != null) {
            return l;
        }
        index++;
        if (index == k) {
            return pRoot;
        }
        TreeNode r = KthNode(pRoot.right, k);
        if (r != null) {
            return r;
        }
        return null;
        
    }


}

---