FilesExpand file tree

 master

/

offer54.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

45 lines (42 loc) · 1.06 KB

 master

/

offer54.java

Copy path

Top

File metadata and controls

• Code
• Blame

45 lines (42 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

45

/**

* [54] 二叉搜素树的第k大节点

*

* 题目: 返回给定二叉搜索树中第 k 大的节点.

*

* 思路: 二叉搜索树的中序遍历序列是升序的, 所以只要将其左中右的遍历顺序改为右中左, 其遍历序列就会变成降序,

* 此时遍历 k 个节点即可得到第 k 大的节点.

*/

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

/**

* 时间复杂度: O(n)

* 空间复杂度: O(n)

*/

private int cnt = 0;

private int ret = 0;

public int kthLargest(TreeNode root, int k) {

inorder(root, k);

return ret;

}

private void inorder(TreeNode root, int k) {

if (root == null) {

return;

}

// traversal order is right to mid to left.

inorder(root.right, k);

cnt++;

if (cnt == k) {

ret = root.val;

return;

}

inorder(root.left, k);

}

}