黑马程序员技术交流社区

标题: 【上海校区】算法题（二十四）：找到BST中的第k小的数 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:30
标题: 【上海校区】算法题（二十四）：找到BST中的第k小的数
题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

分析
常见方法是用中序遍历算法来做，中序遍历时，输出顺序正好是由小到大。

代码
import java.util.Stack;

public class KthNode {

       
        public static int index = 0;
        // 递归版本
        public static TreeNode kthNode1(TreeNode root, int k) {
                if (root != null) {
                        TreeNode node = kthNode1(root.left, k);
                        if (node != null) {
                                return node;
                        }
                        index++;
                        if (index == k) {
                                return root;
                        }
                        node = kthNode1(root.right, k);
                        if (node != null) {
                                return node;
                        }
                }
                return null;
        }

        // 非递归版本
        public static TreeNode kthNode2(TreeNode root, int k) {
                if (root == null || k == 0)
                        return null;
                int count = 0;
                Stack<TreeNode> stack = new Stack<>();
                while (root != null || !stack.isEmpty()) {
                        while (root != null) {
                                stack.push(root);
                                root = root.left;
                        }
                        root = stack.pop();
                        count++;
                        if (count == k)
                                return root;
                        root = root.right;
                }
                return null;
        }

}

---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/83660147
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:47
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2