java语言--二叉搜索树的第k个结点

冷不防 2022-10-06 08:59 157阅读 0赞

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

[牛客网地址][Link 1]

2、问题分析：题目给出的是该二叉树的层序遍历结果。实际如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

可以看到，4是按大小排序时，第3个节点。如果K=3，即4为所求的值。而对应大小排序的就是中序遍历，中序遍历结果是\{2,3,4,5,6,7,8\}，**所以本题核心需要使用到中序遍历。**然后对中序遍历的结果中，取第K个元素即可。这里可以使用数字或者集合存储遍历结果，然后取第k个，但是会产生额外的空间复杂度，当然也可以使用一个变量记录遍历的节点数，当遍历到K个节点时即为所求。

3、核心代码实现：

public class JZ62ErChaShuSouDIKJieDian {
    
        //题目给出的是该二叉树的前序遍历结果。 {5,3,7,2,4,6,8}
        public static void main(String[] args) {
            TreeNode treeNode = new TreeNode(5);
            treeNode.left = new TreeNode(3);
            treeNode.left.left = new TreeNode(2);
            treeNode.left.right = new TreeNode(4);
            treeNode.right = new TreeNode(7);
            treeNode.right.left = new TreeNode(6);
            treeNode.right.right = new TreeNode(8);
            TreeNode treeNode1 = kthNode1(treeNode, 3);
            System.out.println(treeNode1.val);
        }
    
        private static TreeNode kthNode1(TreeNode treeNode, int k) {
            if(treeNode == null || k < 1){
                return treeNode;
            }
            Stack<TreeNode> stack = new Stack<>();//建立栈
            TreeNode cur = treeNode;
            while (!stack.isEmpty() || cur != null){
                if(cur != null){
                    stack.push(cur);
                    cur = cur.left;//当前节点不为null，应该寻找左儿子
                }else {
                    cur = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。
                    if(--k == 0){//计数器功能
                        return cur;
                    }
                    cur = cur.right;//中序遍历查询右儿子，即左边暂时没有最小的，去右边找。
                }
            }
            return null;
        }
    
        static class TreeNode {
            int val = 0;
            TreeNode left = null;
            TreeNode right = null;
            public TreeNode(int val) {
                this.val = val;
            }
        }
     
    }

4、执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][] 到此，二叉搜索树的第K个节点查找的算法已经实现，大家多多练习。

[Link 1]: https://www.nowcoder.com/ta/coding-interviews
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/83077c785efd47a89b9a3833de01fc79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221005/7cd9e67783d64d95a98e237f6693535f.png