题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
解法一：中序遍历递归
public class Solution {
int num
= 0;
TreeNode
KthNode(TreeNode pRoot
, int k
) {
if(pRoot
!=null
){
TreeNode node
= KthNode(pRoot
.left
,k
);
if(node
!=null
) return node
;
num
++;
if(num
==k
) return pRoot
;
node
= KthNode(pRoot
.right
,k
);
if(node
!=null
) return node
;
}
return null
;
}
}
解法二：中序遍历非递归
import java
.util
.*
;
public class Solution {
TreeNode
KthNode(TreeNode pRoot
, int k
) {
if(pRoot
==null
) return null
;
Stack
<TreeNode> s
= new Stack<>();
TreeNode p
= pRoot
;
int num
= 0;
while(!s
.isEmpty()||p
!=null
){
while(p
!=null
){
s
.push(p
);
p
= p
.left
;
}
p
= s
.pop();
num
++;
if(num
==k
) return p
;
p
= p
.right
;
}
return null
;
}
}
