-
Notifications
You must be signed in to change notification settings - Fork 21
/
Convert Binary Search Tree to Sorted Doubly Linked List (extra space).java
executable file
·111 lines (93 loc) · 2.73 KB
/
Convert Binary Search Tree to Sorted Doubly Linked List (extra space).java
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
M
1531695678
tags: Tree, Linked List, Stack
time: O(n)
space: O(n)
给一个BST, convert成 sorted doubly DoublyListNode.
#### Inorder Traversal, Linked List
- 会iterative traverse Binary Search Tree(Stack && handle left-dig-down)
- create Doubly-ListNode, 注意用一个dNode作为tail node of the list
##### Iterative inorder traversal
- 在check right node的事后,
- 不论right == null or != null, 每次都要强行move to right.
- 如果不node = node.right,
- 很可能发生窘境:
- node always = stack.top(), 然后stack.top()一直是一开始把left 全部遍历的内容。所以就会infinite loop, 永远在左边上下上下。
```
/*
LintCode
Convert a binary search tree to doubly linked list with in-order traversal.
Example
Given a binary search tree:
4
/ \
2 5
/ \
1 3
return 1<->2<->3<->4<->5
Tags Expand
Linked List
*/
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* Definition for Doubly-ListNode.
* public class DoublyListNode {
* int val;
* DoublyListNode next, prev;
* DoublyListNode(int val) {
* this.val = val;
* this.next = this.prev = null;
* }
* }
*/
/*
Thoughts:
Inorder with 1 stack: peek add left till end, pop and add, then push right node.
Everytime when pop out a node and add, make it a new boubllistnode
tail.next = curr
curr.pre = tail.next
tail = tail.next
boarder case: if null, return a null.
*/
public class Solution {
public DoublyListNode bstToDoublyList(TreeNode root) {
if (root == null) {
return null;
}
//Init stack
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
stack.push(node);
//Create DoublyListNode header
DoublyListNode dummy = new DoublyListNode(0);
DoublyListNode tail = dummy;
while(!stack.isEmpty()) {
// Add left till leaf
while (node != null && node.left != null) {
stack.push(node.left);
node = node.left;
}
//add node, and doubly link with prev node
node = stack.pop();
DoublyListNode curr = new DoublyListNode(node.val);
tail.next = curr;
curr.prev = tail;
tail = tail.next;
//check right node and add to stack
node = node.right;
if (node != null) {
stack.push(node);
}
}
return dummy.next;
}
}
```