【上海校区】算法题(二十四):找到BST中的第k小的数

python 未结 0 52
2021-07-22 14:47
悬赏:89
题目描述
给定一棵二叉搜索树,请找出其中的第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
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复