FilesExpand file tree

 master

/

offer36.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (57 loc) · 1.44 KB

 master

/

offer36.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (57 loc) · 1.44 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

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

/**

* [36] 二叉搜索树与双向链表

*

* 题目: 将给定二叉搜索树转换成一个排序的循环双向链表. 要求不能创建任何新的节点, 只能调整树中节点指针的指向.

*

* 思路: 因为要创建排序的链表, 所以中序遍历给定二叉树, 依次将遍历到的节点连接起来.

*/

/*

// Definition for a Node.

class Node {

public int val;

public Node left;

public Node right;

public Node() {}

public Node(int _val) {

val = _val;

}

public Node(int _val,Node _left,Node _right) {

val = _val;

left = _left;

right = _right;

}

};

*/

class Solution {

/**

* 时间复杂度: O(n)

* 空间复杂度: O(n)

*/

// use dummy as the header of the list.

private Node dummy = new Node(-1);

// use tail point current list's last node,

// for connect node to list.

private Node tail = dummy;

public Node treeToDoublyList(Node root) {

if (root == null) {

return null;

}

dfs(root);

// make list to be a circle.

Node head = dummy.right;

head.left = tail;

tail.right = head;

return head;

}

private void dfs(Node root) {

if (root == null) {

return;

}

dfs(root.left);

// connect current node to list.

tail.right = root;

root.left = tail;

tail = root;

dfs(root.right);

}

}