一：排序链表
1. 自顶向下归并排序
对链表不断切分，然后使用合并两个有序链表的方式合并
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
| class Solution {
public:
ListNode* sortList(ListNode* head) {
return recursion(head, nullptr);
}
ListNode* recursion(ListNode* left, ListNode* right)
{
if (left == nullptr || left->next == nullptr) return left;
if (left->next == right)
{
left->next = nullptr;
return left;
}
ListNode* slow = left, *fast = left;
while (fast != right)
{
slow = slow->next;
fast = fast->next;
if (fast != right) fast = fast->next;
}
ListNode* mid = slow;
ListNode* leftNew = recursion(left, mid);
ListNode* rightNew = recursion(mid, right);
return MergeTwoLists(leftNew, rightNew);
}
ListNode* MergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* preNode = new ListNode(0);
ListNode* cur = preNode;
if (!list1) return list2;
if (!list2) return list1;
while (list1 != nullptr && list2 != nullptr)
{
if (list1->val < list2->val)
{
cur->next = list1;
list1 = list1->next;
}
else
{
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 == nullptr ? list2 : list1;
return preNode->next;
}
};
|
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
| class Solution {
public ListNode sortList(ListNode head) {
return recursion(head, null);
}
public ListNode recursion(ListNode left, ListNode right)
{
if (left == null || left.next == null) return left;
if (left.next == right)
{
left.next = null;
return left;
}
ListNode slow = left, fast = left;
while (fast != right)
{
slow = slow.next;
fast = fast.next;
if (fast != right) fast = fast.next;
}
ListNode mid = slow;
ListNode leftNew = recursion(left, mid);
ListNode rightNew = recursion(mid, right);
return MergeTwoLists(leftNew, rightNew);
}
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
ListNode preNode = new ListNode(0);
ListNode cur = preNode;
if (list1 == null) return list2;
if (list2 == null) return list1;
while (list1 != null && list2 != null)
{
if (list1.val < list2.val)
{
cur.next = list1;
list1 = list1.next;
}
else
{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 == null ? list2 : list1;
return preNode.next;
}
}
|
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
| class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.recursion(head, None)
def recursion(self, left, right):
if (left == None or left.next == None): return left
if (left.next == right):
left.next = None
return left
slow, fast = left, left
while (fast != right):
slow = slow.next
fast = fast.next
if (fast != right): fast = fast.next
mid = slow
leftNew = self.recursion(left, mid)
rightNew = self.recursion(mid, right)
return self.MergeTwoLists(leftNew, rightNew)
def MergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
preNode = ListNode(0)
cur = preNode
if not list1:
return list2
if not list2:
return list1
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
else:
cur.next = list2
return preNode.next
|
2. 自底向上归并排序
第一层处理两个节点，将它们断开并排序，第二层结束处理四个节点，其中的两两已经处理好，是有序链表，因此可直接排序，依次迭代
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
| class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == nullptr) return head;
int length = 0;
ListNode* temp = head;
ListNode* pre = new ListNode(0, head);
while (temp != nullptr)
{
++length;
temp = temp->next;
}
for (int sub = 1; sub < length; sub *= 2)
{
ListNode* preCur = pre;
ListNode* cur = pre->next;
while (cur != nullptr)
{
ListNode* node1 = cur;
for (int i = 1; i < sub && cur->next != nullptr; ++i) cur = cur->next;
ListNode* node2 = cur->next;
cur->next = nullptr;
cur = node2;
for (int i = 1; i < sub && cur != nullptr && cur->next !=nullptr; ++i) cur = cur->next;
ListNode* next = nullptr;
if (cur != nullptr)
{
next = cur->next;
cur->next = nullptr;
cur = next;
}
preCur->next = MergeTwoLists(node1, node2);
while (preCur->next != nullptr) preCur = preCur->next;
}
}
return pre->next;
}
ListNode* MergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* preNode = new ListNode(0);
ListNode* cur = preNode;
if (!list1) return list2;
if (!list2) return list1;
while (list1 != nullptr && list2 != nullptr)
{
if (list1->val < list2->val)
{
cur->next = list1;
list1 = list1->next;
}
else
{
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 == nullptr ? list2 : list1;
return preNode->next;
}
};
|
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
| class Solution {
public ListNode sortList(ListNode head) {
if (head == null) return head;
int length = 0;
ListNode temp = head;
ListNode pre = new ListNode(0, head);
while (temp != null)
{
++length;
temp = temp.next;
}
for (int sub = 1; sub < length; sub *= 2)
{
ListNode preCur = pre;
ListNode cur = pre.next;
while (cur != null)
{
ListNode node1 = cur;
for (int i = 1; i < sub && cur.next != null; ++i) cur = cur.next;
ListNode node2 = cur.next;
cur.next = null;
cur = node2;
for (int i = 1; i < sub && cur != null && cur.next !=null; ++i) cur = cur.next;
ListNode next = null;
if (cur != null)
{
next = cur.next;
cur.next = null;
cur = next;
}
preCur.next = MergeTwoLists(node1, node2);
while (preCur.next != null) preCur = preCur.next;
}
}
return pre.next;
}
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
ListNode preNode = new ListNode(0);
ListNode cur = preNode;
if (list1 == null) return list2;
if (list2 == null) return list1;
while (list1 != null && list2 != null)
{
if (list1.val < list2.val)
{
cur.next = list1;
list1 = list1.next;
}
else
{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 == null ? list2 : list1;
return preNode.next;
}
}
|
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
| class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if (head == None): return head
length = 0
temp = head
pre = ListNode(0, head)
while (temp != None):
length += 1
temp = temp.next
sub = 1
while (sub < length):
preCur = pre
cur = pre.next
while (cur != None):
node1 = cur
for i in range(1, sub):
if cur.next:
cur = cur.next
else:
break
node2 = cur.next
cur.next = None
cur = node2
for i in range(1, sub):
if cur and cur.next:
cur = cur.next
else:
break
next = None
if (cur != None):
next = cur.next
cur.next = None
cur = next
preCur.next = self.MergeTwoLists(node1, node2)
while (preCur.next != None): preCur = preCur.next
sub *= 2
return pre.next
def MergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
preNode = ListNode(0)
cur = preNode
if not list1:
return list2
if not list2:
return list1
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
else:
cur.next = list2
return preNode.next
|
二：LRU缓存
1. 哈希表+双向链表
使用哈希表保存键和双向链表的节点，节点保存键值和前后指针，这样每个操作都为常数
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
| class LRUCache {
private:
struct DoubleList
{
int key;
int value;
DoubleList* pre;
DoubleList* next;
DoubleList() : key(0), value(0), pre(nullptr), next(nullptr) {}
DoubleList(int _key, int _value) : key(_key), value(_value), pre(nullptr), next(nullptr) {}
};
public:
unordered_map<int, DoubleList*> hashMap;
DoubleList* head;
DoubleList* tail;
int capacity = 0;
int size = 0;
LRUCache(int capacity) {
this->capacity = capacity;
head = new DoubleList();
tail = new DoubleList();
head->next = tail;
tail->pre = head;
}
int get(int key) {
if (hashMap.count(key) == false) return -1;
else
{
DoubleList* cur = hashMap[key];
AddToHead(DeleteNode(cur));
return cur->value;
}
}
void put(int key, int value) {
if (hashMap.count(key) == false)
{
DoubleList* newNode = new DoubleList(key, value);
hashMap[key] = newNode;
AddToHead(newNode);
++size;
if (size > capacity)
{
DoubleList* deleteNode = DeleteNode(tail->pre);
hashMap.erase(deleteNode->key);
delete deleteNode;
--size;
}
} else
{
DoubleList* cur = hashMap[key];
cur->value = value;
AddToHead(DeleteNode(cur));
}
}
DoubleList* DeleteNode(DoubleList* node)
{
node->next->pre = node->pre;
node->pre->next = node->next;
return node;
}
void AddToHead(DoubleList* node)
{
node->pre = head;
node->next = head->next;
head->next = node;
node->next->pre = node;
}
};
|
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
| class LRUCache {
class DoubleList
{
int key;
int value;
DoubleList pre;
DoubleList next;
public DoubleList() {}
public DoubleList(int _key, int _value) {key = _key; value = _value;}
}
Map<Integer, DoubleList> hashMap = new HashMap<>();
DoubleList head;
DoubleList tail;
int capacity = 0;
int size = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new DoubleList();
tail = new DoubleList();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (hashMap.containsKey(key) == false) return -1;
else
{
DoubleList cur = hashMap.get(key);
AddToHead(DeleteNode(cur));
return cur.value;
}
}
public void put(int key, int value) {
if (hashMap.containsKey(key) == false)
{
DoubleList newNode = new DoubleList(key, value);
hashMap.put(key, newNode);
AddToHead(newNode);
++size;
if (size > capacity)
{
DoubleList deleteNode = DeleteNode(tail.pre);
hashMap.remove(deleteNode.key);
--size;
}
} else
{
DoubleList cur = hashMap.get(key);
cur.value = value;
AddToHead(DeleteNode(cur));
}
}
public DoubleList DeleteNode(DoubleList node)
{
node.next.pre = node.pre;
node.pre.next = node.next;
return node;
}
public void AddToHead(DoubleList node)
{
node.pre = head;
node.next = head.next;
head.next = node;
node.next.pre = node;
}
}
|
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
| class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.hashMap = dict()
self.head = DoubleList()
self.tail = DoubleList()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if (key not in self.hashMap): return -1
else:
cur = self.hashMap[key]
self.AddToHead(self.DeleteNode(cur))
return cur.value
def put(self, key: int, value: int) -> None:
if (key not in self.hashMap):
newNode = DoubleList(key, value)
self.hashMap[key] = newNode
self.AddToHead(newNode)
self.size += 1
if (self.size > self.capacity):
deleteNode = self.DeleteNode(self.tail.pre)
self.hashMap.pop(deleteNode.key)
self.size -= 1
else:
cur = self.hashMap[key]
cur.value = value
self.AddToHead(self.DeleteNode(cur))
def DeleteNode(self, node):
node.next.pre = node.pre
node.pre.next = node.next
return node
def AddToHead(self, node):
node.pre = self.head
node.next = self.head.next
self.head.next = node
node.next.pre = node
class DoubleList:
def __init__(self, key = 0, value = 0):
self.key = key
self.value = value
self.prev = None
self.next = None
|
三：二叉树的层序遍历
1. 广度优先搜索
用队列表示每一层，逐层遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;
queue<TreeNode*> queueTree;
queueTree.push(root);
while (queueTree.empty() == false)
{
int size = queueTree.size();
result.emplace_back(vector<int>());
for (int i = 0; i < size; ++i)
{
TreeNode* newNode = queueTree.front();
queueTree.pop();
result.back().emplace_back(newNode->val);
if (newNode->left) queueTree.push(newNode->left);
if (newNode->right) queueTree.push(newNode->right);
}
}
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
Queue<TreeNode> queueTree = new LinkedList<>();
queueTree.offer(root);
while (queueTree.isEmpty() == false)
{
int size = queueTree.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; ++i)
{
TreeNode newNode = queueTree.poll();
level.add(newNode.val);
if (newNode.left != null) queueTree.offer(newNode.left);
if (newNode.right != null) queueTree.offer(newNode.right);
}
result.add(level);
}
return result;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
result = []
if (root == None): return result
queueTree = deque([root])
while (queueTree):
size = len(queueTree)
level = []
for _ in range(size):
newNode = queueTree.popleft()
level.append(newNode.val)
if (newNode.left != None): queueTree.append(newNode.left)
if (newNode.right != None): queueTree.append(newNode.right)
result.append(level)
return result
|
四：验证二叉搜索树
1. 递归
参考二叉树的中序遍历的递归写法，这里多了对数据大小的判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool isValidBST(TreeNode* root) {
return recursion(root, LONG_MIN, LONG_MAX);
}
bool recursion(TreeNode* node, long long min, long long max)
{
if (node == nullptr) return true;
if (node->val <= min || node->val >= max) return false;
bool flagLeft = recursion(node->left, min, node->val);
bool flagRight = recursion(node->right, node->val, max);
return flagLeft && flagRight;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isValidBST(TreeNode root) {
return recursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean recursion(TreeNode node, long min, long max)
{
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
boolean flagLeft = recursion(node.left, min, node.val);
boolean flagRight = recursion(node.right, node.val, max);
return flagLeft && flagRight;
}
}
|
1
2
3
4
5
6
7
8
9
| class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def recursion(node, min, max):
if (node == None): return True
if (node.val <= min or node.val >= max): return False
flagLeft = recursion(node.left, min, node.val)
flagRight = recursion(node.right, node.val, max)
return flagLeft and flagRight
return recursion(root, float('-inf'), float('inf'))
|
2. 中序遍历
参考二叉树的中序遍历的迭代写法，这里多了对数据大小的判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> treeStack;
long long min = (long long)INT_MIN - 1;
while (root != nullptr || !treeStack.empty())
{
while (root != nullptr)
{
treeStack.push(root);
root = root->left;
}
root = treeStack.top();
treeStack.pop();
if (root -> val <= min) return false;
min = root -> val;
root = root->right;
}
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> treeDeque = new ArrayDeque<TreeNode>();
double min = -Double.MAX_VALUE - 1;
while (root != null || !treeDeque.isEmpty())
{
while (root != null)
{
treeDeque.push(root);
root = root.left;
}
root = treeDeque.pop();
if (root.val <= min) return false;
min = root.val;
root = root.right;
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
treeStack = []
min = float('-inf')
while root is not None or treeStack:
while root is not None:
treeStack.append(root)
root = root.left
root = treeStack.pop()
if (root.val <= min): return False
min = root.val
root = root.right
return True
|
五：二叉搜索树中第 K 小的元素
1. 中序遍历
利用中序遍历得到有序数组，找到数组中的第K个元素即可。迭代用栈管理，栈弹出的顺序就是有序列表，因此第K个就是需要的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> treeStack;
while (root != nullptr || !treeStack.empty())
{
while (root != nullptr)
{
treeStack.push(root);
root = root->left;
}
root = treeStack.top();
treeStack.pop();
--k;
if (k == 0) break;
root = root->right;
}
return root->val;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> treeDeque = new ArrayDeque<TreeNode>();
double min = -Double.MAX_VALUE - 1;
while (root != null || !treeDeque.isEmpty())
{
while (root != null)
{
treeDeque.push(root);
root = root.left;
}
root = treeDeque.pop();
--k;
if (k == 0) break;
root = root.right;
}
return root.val;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
treeStack = []
while root is not None or treeStack:
while root is not None:
treeStack.append(root)
root = root.left
root = treeStack.pop()
k -= 1
if (k == 0): break
root = root.right
return root.val
|
2. 记录子树的节点
把每个节点的左右子树的节点数量记录，此时只需要判断k与子树节点数量的大小，因为左子树一定小于当前节点，右子树大于当前节点。适用于频繁寻找k值
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
| class Solution {
public:
unordered_map<TreeNode*, int> hashMap;
TreeNode* root;
int kthSmallest(TreeNode* root, int k) {
this->root = root;
CountNum(root);
return SearchTarget(k);
}
int CountNum(TreeNode* node)
{
if (node == nullptr) return 0;
hashMap[node] = 1 + CountNum(node->left) + CountNum(node->right);
return hashMap[node];
}
int GetNum(TreeNode* node)
{
if (node != nullptr && hashMap.count(node)) return hashMap[node];
else return 0;
}
int SearchTarget(int k)
{
TreeNode* node = root;
while (node != nullptr)
{
int leftNum = GetNum(node->left);
if (leftNum < k - 1)
{
node = node->right;
k -= leftNum + 1;
} else if (leftNum > k - 1) node = node->left;
else break;
}
return node->val;
}
};
|
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
| class Solution {
public Map<TreeNode, Integer> hashMap = new HashMap<>();
public TreeNode root;
public int kthSmallest(TreeNode root, int k) {
this.root = root;
CountNum(root);
return SearchTarget(k);
}
public int CountNum(TreeNode node)
{
if (node == null) return 0;
hashMap.put(node, 1 + CountNum(node.left) + CountNum(node.right));
return hashMap.get(node);
}
public int GetNum(TreeNode node)
{
if (node != null && hashMap.containsKey(node)) return hashMap.get(node);
else return 0;
}
public int SearchTarget(int k)
{
TreeNode node = root;
while (node != null)
{
int leftNum = GetNum(node.left);
if (leftNum < k - 1)
{
node = node.right;
k -= leftNum + 1;
} else if (leftNum > k - 1) node = node.left;
else break;
}
return node.val;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
self.hashMap = {}
self.root = root
self.CountNum(self.root)
return self.SearchTarget(k)
def CountNum(self, node):
if (node == None): return 0
self.hashMap[node] = 1 + self.CountNum(node.left) + self.CountNum(node.right)
return self.hashMap[node]
def GetNum(self, node):
if (node != None and node in self.hashMap): return self.hashMap[node]
else: return 0
def SearchTarget(self, k):
node = self.root
while (node != None):
leftNum = self.GetNum(node.left)
if (leftNum < k - 1):
node = node.right
k -= leftNum + 1
elif (leftNum > k - 1): node = node.left
else: break
return node.val
|
3. 平衡二叉搜索树
官方给的题解太长了，使用了经典的AVL树数据结构，并添加了一些常用的操作，没必要，简化一下吧
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
| struct Node {
int val;
Node * parent;
Node * left;
Node * right;
int size;
int height;
Node(int val, Node * parent) {
this->val = val;
this->parent = parent;
this->left = nullptr;
this->right = nullptr;
this->height = 0;
this->size = 1;
}
};
class AVL {
public:
Node * root;
AVL(vector<int> & vals) {
if (!vals.empty()) {
root = build(vals, 0, vals.size() - 1, nullptr);
}
}
Node * build(vector<int> & vals, int l, int r, Node * parent) {
int m = (l + r) >> 1;
Node * node = new Node(vals[m], parent);
if (l <= m - 1) {
node->left = build(vals, l, m - 1, node);
}
if (m + 1 <= r) {
node->right = build(vals, m + 1, r, node);
}
recompute(node);
return node;
}
void recompute(Node * node) {
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
node->size = 1 + getSize(node->left) + getSize(node->right);
}
static int getHeight(Node * node) {
return node != nullptr ? node->height : 0;
}
static int getSize(Node * node) {
return node != nullptr ? node->size : 0;
}
int kthSmallest(int k) {
Node * node = root;
while (node != nullptr) {
int left = getSize(node->left);
if (left < k - 1) {
node = node->right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node->left;
}
}
return node->val;
}
};
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> inorderList;
inorder(root, inorderList);
AVL avl(inorderList);
return avl.kthSmallest(k);
}
void inorder(TreeNode * node, vector<int> & inorderList) {
if (node->left != nullptr) {
inorder(node->left, inorderList);
}
inorderList.push_back(node->val);
if (node->right != nullptr) {
inorder(node->right, inorderList);
}
}
};
|
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
| class Node {
int val;
Node parent;
Node left;
Node right;
int size;
int height;
Node(int val, Node parent) {
this.val = val;
this.parent = parent;
this.left = null;
this.right = null;
this.height = 0;
this.size = 1;
}
}
class AVL {
Node root;
AVL(List<Integer> vals) {
if (!vals.isEmpty()) {
root = build(vals, 0, vals.size() - 1, null);
}
}
Node build(List<Integer> vals, int l, int r, Node parent) {
if (l > r) {
return null;
}
int m = l + (r - l) / 2;
Node node = new Node(vals.get(m), parent);
node.left = build(vals, l, m - 1, node);
node.right = build(vals, m + 1, r, node);
recompute(node);
return node;
}
void recompute(Node node) {
if (node == null) return;
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
node.size = 1 + getSize(node.left) + getSize(node.right);
}
static int getHeight(Node node) {
return node != null ? node.height : 0;
}
static int getSize(Node node) {
return node != null ? node.size : 0;
}
int kthSmallest(int k) {
Node node = root;
while (node != null) {
int left = getSize(node.left);
if (left < k - 1) {
node = node.right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node.left;
}
}
return node.val;
}
}
class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> inorderList = new ArrayList<>();
inorder(root, inorderList);
if (inorderList.isEmpty() || k <= 0 || k > inorderList.size()) {
return -1;
}
AVL avl = new AVL(inorderList);
return avl.kthSmallest(k);
}
void inorder(TreeNode node, List<Integer> inorderList) {
if (node == null) {
return;
}
inorder(node.left, inorderList);
inorderList.add(node.val);
inorder(node.right, inorderList);
}
}
|
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
| class Node:
def __init__(self, val: int, parent: Optional['Node'] = None):
self.val = val
self.parent = parent
self.left = None
self.right = None
self.height = 0
self.size = 1
class AVL:
def __init__(self, vals: List[int]):
self.root: Optional[Node] = None
if vals:
self.root = self.build(vals, 0, len(vals) - 1, None)
def build(self, vals: List[int], l: int, r: int, parent: Optional[Node]) -> Optional[Node]:
if l > r:
return None
m = (l + r) // 2
node = Node(vals[m], parent)
node.left = self.build(vals, l, m - 1, node)
node.right = self.build(vals, m + 1, r, node)
self.recompute(node)
return node
def recompute(self, node: Node):
if node is None:
return
left_height = AVL.get_height(node.left)
right_height = AVL.get_height(node.right)
node.height = 1 + max(left_height, right_height)
node.size = 1 + AVL.get_size(node.left) + AVL.get_size(node.right)
@staticmethod
def get_height(node: Optional[Node]) -> int:
return node.height if node else 0
@staticmethod
def get_size(node: Optional[Node]) -> int:
return node.size if node else 0
def kthSmallest(self, k: int) -> int:
node = self.root
while node:
left_size = AVL.get_size(node.left)
if left_size < k - 1:
k -= left_size + 1
node = node.right
elif left_size == k - 1:
return node.val
else:
node = node.left
return -1
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
inorder_list: List[int] = []
self._inorder(root, inorder_list)
if not inorder_list or k <= 0 or k > len(inorder_list):
return -1
avl = AVL(inorder_list)
return avl.kthSmallest(k)
def _inorder(self, node: Optional[TreeNode], inorder_list: List[int]):
if node is None:
return
self._inorder(node.left, inorder_list)
inorder_list.append(node.val)
self._inorder(node.right, inorder_list)
|
