剑指offer 62.树 二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)    中,按结点数值大小顺序第三小结点的值为4。

解题思路

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

代码如下

   int index = 0; //计数器
            TreeNode KthNode(TreeNode root, int k)
            {
                if(root != null){ //中序遍历寻找第k个
                    TreeNode node = KthNode(root.left,k);
                    if(node != null)
                        return node;
                    index ++;
                    if(index == k)
                        return root;
                    node = KthNode(root.right,k);
                    if(node != null)
                        return node;
                }
                return null;
            }

 

上一篇:《剑指Offer(第二版)》面试题62. 圆圈中最后剩下的数字


下一篇:日记o3o