题目：给定一个二叉搜索树(BST)，找到树中第K小的节点。
出题人：阿里巴巴出题专家：文景／阿里云CDN资深技术专家
参考答案：本文章由网络网友开源获得，侵权联系删除
*考察点
基础数据结构的理解和编码能力
递归使用
*示例
5/\36/\24/1
说明：保证输入的K满足1=K=(节点数目）
解法1：树相关的题目，第一眼就想到递归求解，左右子树分别遍历。联想到二叉搜索树的性质，root大于左子树，小于右子树，如果左子树的节点数目等于K-1，那么root就是结果，否则如果左子树节点数目小于K-1，那么结果必然在右子树，否则就在左子树。因此在搜索的时候同时返回节点数目，跟K做对比，就能得出结果了。
/***Definitionforabinarytreenode.**/publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}classSolution{privateclassResultType{booleanfound;//是否找到intval;//节点数目ResultType(booleanfound,intval){this.found=found;this.val=val;}}publicintkthSmallest(TreeNoderoot,intk){returnkthSmallestHelper(root,k).val;}privateResultTypekthSmallestHelper(TreeNoderoot,intk){if(root==null){returnnewResultType(false,0);}ResultTypeleft=kthSmallestHelper(root.left,k);//左子树找到，直接返回if(left.found){returnnewResultType(true,left.val);}//左子树的节点数目=K-1，结果为root的值if(k-left.val==1){returnnewResultType(true,root.val);}//右子树寻找ResultTyperight=kthSmallestHelper(root.right,k-left.val-1);if(right.found){returnnewResultType(true,right.val);}//没找到，返回节点总数returnnewResultType(false,left.val+1+right.val);}}
解法2：基于二叉搜索树的特性，在中序遍历的结果中，第k个元素就是本题的解。最差的情况是k节点是bst的最右叶子节点，不过每个节点的遍历次数最多是1次。遍历并不是需要全部做完，使用计数的方式，找到第k个元素就可以退出。下面是go的一个简单实现。
//BSTisbinarysearchtreetypeBSTstruct{ key,valueint left,right*BST}func(bst*BST)setLeft(b*BST){ bst.left=b}func(bst*BST)setRight(b*BST){ bst.right=b}//count查找bst第k个节点的值，未找到就返回0funccount(bst*BST,kint)int{ ifk1{ return0 } c:=0 ok,value:=countRecursive(bst,c,k) ifok{ returnvalue } return0}//countRecurisive对bst使用中序遍历//用计数方式控制退出遍历，参数c就是已遍历节点数funccountRecursive(bst*BST,c*int,kint)(bool,int){ ifbst.left!=nil{ ok,value:=countRecursive(bst.left,c,k) ifok{ returnok,value } } if*c==k-1{ returntrue,bst.value } *c++ ifbst.right!=nil{ ok,value:=countRecursive(bst.right,c,k) ifok{ returnok,value } } returnfalse,0}//下面是测试代码，覆盖了退化的情况和普通bstfunccreateBST1()*BST{ b1:=BST{key:1,value:10} b2:=BST{key:2,value:20} b3:=BST{key:3,value:30} b4:=BST{key:4,value:40} b5:=BST{key:5,value:50} b6:=BST{key:6,value:60} b7:=BST{key:7,value:70} b8:=BST{key:8,value:80} b9:=BST{key:9,value:90} b9.setLeft(b8) b8.setLeft(b7) b7.setLeft(b6) b6.setLeft(b5) b5.setLeft(b4) b4.setLeft(b3) b3.setLeft(b2) b2.setLeft(b1) returnb9}funccreateBST2()*BST{ b1:=BST{key:1,value:10} b2:=BST{key:2,value:20} b3:=BST{key:3,value:30} b4:=BST{key:4,value:40} b5:=BST{key:5,value:50} b6:=BST{key:6,value:60} b7:=BST{key:7,value:70} b8:=BST{key:8,value:80} b9:=BST{key:9,value:90} b1.setRight(b2) b2.setRight(b3) b3.setRight(b4) b4.setRight(b5) b5.setRight(b6) b6.setRight(b7) b7.setRight(b8) b8.setRight(b9) returnb1}funccreateBST3()*BST{ b1:=BST{key:1,value:10} b2:=BST{key:2,value:20} b3:=BST{key:3,value:30} b4:=BST{key:4,value:40} b5:=BST{key:5,value:50} b6:=BST{key:6,value:60} b7:=BST{key:7,value:70} b8:=BST{key:8,value:80} b9:=BST{key:9,value:90} b5.setLeft(b3) b5.setRight(b7) b3.setLeft(b2) b3.setRight(b4) b2.setLeft(b1) b7.setLeft(b6) b7.setRight(b8) b8.setRight(b9) returnb5}funccreateBST4()*BST{ b:=BST{key:1,value:10} last:=b fori:=2;i;i++{ n:=BST{key:i,value:i*10} last.setRight(n) last=n } returnb}funccreateBST5()*BST{ b:=BST{key:,value:0} last:=b fori:=;i0;i--{ n:=BST{key:i,value:i*10} last.setLeft(n) last=n } returnb}funccreateBST6()*BST{ b:=BST{key:,value:0} last:=b fori:=;i0;i--{ n:=BST{key:i,value:i*10} last.setLeft(n) last=n } last=b fori:=;i;i++{ n:=BST{key:i,value:i*10} last.setRight(n) last=n } returnb}funcTestK(t*testing.T){ bst1:=createBST1() bst2:=createBST2() bst3:=createBST3() bst4:=createBST4() check(t,bst1,1,10) check(t,bst1,2,20) check(t,bst1,3,30) check(t,bst1,4,40) check(t,bst1,5,50) check(t,bst1,6,60) check(t,bst1,7,70) check(t,bst1,8,80) check(t,bst1,9,90) check(t,bst2,1,10) check(t,bst2,2,20) check(t,bst2,3,30) check(t,bst2,4,40) check(t,bst2,5,50) check(t,bst2,6,60) check(t,bst2,7,70) check(t,bst2,8,80) check(t,bst2,9,90) check(t,bst3,1,10) check(t,bst3,2,20) check(t,bst3,3,30) check(t,bst3,4,40) check(t,bst3,5,50) check(t,bst3,6,60) check(t,bst3,7,70) check(t,bst3,8,80) check(t,bst3,9,90) check(t,bst4,1,10) check(t,bst4,2,20) check(t,bst4,3,30) check(t,bst4,4,40) check(t,bst4,5,50) check(t,bst4,6,60) check(t,bst4,7,70) check(t,bst4,8,80) check(t,bst4,9,90) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0) check(t,bst4,,0)}funccheck(t*testing.T,b*BST,k,valueint){ t.Helper() checkCall(t,b,k,value,count) //此处可添加其他解法的实现}funccheckCall(t*testing.T,b*BST,k,valueint,findfunc(bst*BST,kthint)int){ t.Helper() got:=find(b,k) ifgot!=value{ t.Fatalf("want:%d,got:%d",value,got) }}