给定一棵二叉搜索树,找出其中的第k小的结点。例如(5,3,7,2,4,6,8)中,按结点数值大小顺序第3小的结点值为4。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45import java.util.Stack; public class T_62_KthNode { int count = 0; //递归,中序遍历 TreeNode KthNode(TreeNode pRoot, int k) { if (pRoot != null) { TreeNode node = KthNode(pRoot.left, k); if (node != null) { return node; } count++; if (count == k) { return pRoot; } node = KthNode(pRoot.right, k); if (node != null) { return node; } } return null; } //非递归,中序遍历 TreeNode KthNode2(TreeNode pRoot, int k) { if (pRoot != null) { Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || pRoot != null) { if (pRoot != null) { stack.push(pRoot); pRoot = pRoot.left; } else { pRoot = stack.pop(); count++; if (count == k) { return pRoot; } pRoot = pRoot.right; } } } return null; } }
最后
以上就是甜美流沙最近收集整理的关于剑指offer——第62题:二叉搜索树的第k小的结点的全部内容,更多相关剑指offer——第62题:二叉搜索树内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复