https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked
理论可以用小根堆建堆的
懒得优化了
```js
var mergeKLists = function (lists) {
let newNode = {
next: null
}
const ret = newNode
while (lists.length != 0) {
if(lists==null){
lists.splice(0,1)
continue
}
let maxChain = 0
for (let index = 1; index < lists.length; index++) {
const chain = lists;
if(chain==null){
continue;
}
if (chain.val <= lists.val) {
maxChain = index
}
}
newNode.next = lists
newNode = newNode.next
lists = lists.next
if (lists == null) {
lists.splice(maxChain,1)
}
}
return ret.next
};
```
LRU问题
https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked
打败98%~
!(data/attachment/forum/202409/03/054819knddedccqn9phuhh.png)
```js
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.num = 0;
this.map = new Map();
this.chain = null;
this.tail = null;
};
LRUCache.prototype.appendHead = function (node) {
if (this.tail == node) {
if (node.last == null) {
return;
}
this.tail = this.tail.last;
}
if (node.last) {
node.last.next = node.next;
}
if (node.next&&node.last) {
node.next.last = node.last;
}
if (node != this.chain) {
node.next = this.chain;
this.chain.last = node;
node.last = null;
this.chain = node;
}
};
/**
* @param {number} key
* @Return {number}
*/
LRUCache.prototype.get = function (key) {
const node = this.map.get(key);
if (node == null) {
return -1;
}
this.appendHead(node);
return node.val;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const data = this.map.get(key);
if (data == undefined) {
this.num++;
this.chain = {
last: null,
next: this.chain,
val: value,
key,
};
if (this.chain.next) {
this.chain.next.last = this.chain;
}
if (this.tail == null) {
this.tail = this.chain;
}
this.map.set(key, this.chain);
if (this.num > this.capacity) {
this.map.delete(this.tail.key);
this.tail = this.tail.last;
if (this.tail?.next) {
this.tail.next = null;
}
this.num--;
}
} else {
data.val = value;
this.appendHead(data);
}
};
```
https://leetcode.cn/problems/maximum-depth-of-binary-tree/submissions/560910551/?envType=study-plan-v2&envId=top-100-liked
深度题
秒
```js
var maxDepth = function (root) {
if(root==null){
return 0
}
const leftDeep = maxDepth(root.left);
const rightDeep = maxDepth(root.right);
return Math.max(leftDeep, rightDeep) + 1;
};
```
https://leetcode.cn/problems/invert-binary-tree/submissions/560910572/?envType=study-plan-v2&envId=top-100-liked
翻转问题
秒
```js
var invertTree = function (root) {
if(root==null){
return null
}
const left=invertTree(root.left)
const right=invertTree(root.right)
root.left=right;
root.right=left
return root
};
```
对称题
https://leetcode.cn/problems/symmetric-tree/submissions/560910631/?envType=study-plan-v2&envId=top-100-liked
秒
```js
const check = (left, right) => {
if (left == null || right == null) {
return left === right;
}
if (left.val == right.val) {
return check(left.left, right.right) && check(left.right, right.left);
} else {
return false;
}
};
var isSymmetric = function (root) {
return check(root.left, root.right);
};
```
https://leetcode.cn/problems/diameter-of-binary-tree/submissions/560910726/?envType=study-plan-v2&envId=top-100-liked
直径题，秒
```js
var diameterOfBinaryTree = function (root) {
let max = 0;
const getMax = (node) => {
if (node === null) {
return 0;
}
const left = getMax(node.left);
const right = getMax(node.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
};
getMax(root);
return max;
};
```
https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/560910947/?envType=study-plan-v2&envId=top-100-liked
层序问题，秒
睡觉~
```js
var levelOrder = function (root) {
const ret = [];
let stack = ;
do {
const nextStack = [];
const num = [];
for (let index = 0; index < stack.length; index++) {
const node = stack;
if(node==null){
continue;
}
num.push(node.val);
nextStack.push(node.left, node.right);
}
if(num.length!=0){
ret.push(num);
}
stack=nextStack
} while (stack.length!=0);
return ret;
};
```
数组转二叉树
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/submissions/560911148/?envType=study-plan-v2&envId=top-100-liked
95%执行率秒了
!(data/attachment/forum/202409/03/062742yfqx5fiq9tjgzbfo.png)
```js
var sortedArrayToBST = function (nums) {
const buildTree = (left, right) => {
if (left + 1 == right) {
const leftNode = {
left: null,
right: null,
val: nums,
};
const rightNode = {
left: null,
right: null,
val: nums,
};
rightNode.left = leftNode;
return rightNode;
}else if(left==right){
return {
left:null,
right:null,
val:nums
}
}
const center = left+Math.floor((right - left) / 2);
left = buildTree(left, center - 1);
right = buildTree(center + 1, right);
return {
right,
left,
val: nums,
};
};
return buildTree(0, nums.length - 1);
};
```
https://leetcode.cn/problems/validate-binary-search-tree/submissions/561308458/?envType=study-plan-v2&envId=top-100-liked
中序题
一开始思路错了
```js
var isValidBST = function (root) {
let lastValue = Number.MIN_SAFE_INTEGER;
let status = true;
const checkNode = (root) => {
if(root==null){
return
}
checkNode(root.left);
if (root.val <= lastValue) {
status = false;
return;
}else{
lastValue=root.val
}
checkNode(root.right);
};
checkNode(root)
return status;
};
```
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/submissions/561308503/?envType=study-plan-v2&envId=top-100-liked
缝缝补补又是一道
```js
var kthSmallest = function (root, k) {
let index = 0;
let ret = undefined;
const checkNode = (root) => {
if (root == null || ret !== undefined) {
return;
}
checkNode(root.left);
index++;
if (k == index) {
ret = root.val;
}
checkNode(root.right);
};
checkNode(root);
return ret;
};
```