https://leetcode.cn/problems/binary-tree-right-side-view/submissions/561308653/?envType=study-plan-v2&envId=top-100-liked
缝缝补补又凹一题
```js
var rightSideView = function (root) {
const ret = [];
if(root==null){
return []
}
let stack = ;
do {
const nextStack = [];
for (let index = 0; index < stack.length; index++) {
const node = stack;
if (node == null) {
continue;
}
if(node.left){
nextStack.push(node.left)
}
if(node.right){
nextStack.push(node.right)
}
}
if (stack.length != 0) {
ret.push(stack.val);
}
stack = nextStack;
} while (stack.length != 0);
return ret;
};
```
这题没反应过来就过了...
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/submissions/561311668/?envType=study-plan-v2&envId=top-100-liked
```js
var flatten = function (root) {
if (root == null) {
return null;
}
const handleFlatten = (root) => {
let leftPtr = undefined;
if (root.left) {
leftPtr = handleFlatten(root.left) ?? root.left;
}
let rightPtr = undefined;
if (root.right) {
rightPtr = handleFlatten(root.right) ?? root.right;
}
if (leftPtr) {
leftPtr.left = null;
leftPtr.right = root.right;
}
const left = root.left;
const right = root.right;
root.left = null;
root.right = left ?? right;
return rightPtr ?? leftPtr;
};
handleFlatten(root);
return root;
};
```
边界大法秒！
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/561312292/?envType=study-plan-v2&envId=top-100-liked
```js
var buildTree = function (preorder, inorder) {
const buildNode = (pl, pr, il, ir) => {
if (pl == pr) {
return {
left: null,
right: null,
val: preorder,
};
}
if(pl>pr){
return null
}
const node = {
left: null,
right: null,
val: preorder,
};
const centerIndex = inorder.findIndex((element) => element == node.val);
const newPL = pl + (centerIndex - il);
node.left = buildNode(pl + 1, newPL, il, centerIndex - 1);
node.right = buildNode(newPL + 1, pr, centerIndex + 1, ir);
return node;
};
return buildNode(0, preorder.length - 1, 0, inorder.length - 1);
};
```
打个简单题换换心情
https://leetcode.cn/problems/single-number/?envType=study-plan-v2&envId=top-100-liked
```js
var singleNumber = function(nums) {
let ret=0
for (let index = 0; index < nums.length; index++) {
ret=ret^nums;
}
return ret
};
```
岛屿题，下沉法，秒
https://leetcode.cn/problems/number-of-islands/submissions/561313020/?envType=study-plan-v2&envId=top-100-liked
```js
var numIslands = function (grid) {
let ret = 0;
const clearIsland = (x, y) => {
if (x < 0 || x >= grid.length) {
return;
}
if (y < 0 || y >= grid.length) {
return;
}
if (grid == 1) {
grid = 0;
clearIsland(x - 1, y);
clearIsland(x + 1, y);
clearIsland(x, y + 1);
clearIsland(x, y - 1);
}
};
for (let index = 0; index < grid.length; index++) {
const col = grid;
for (let indey = 0; indey < col.length; indey++) {
const item = col;
if (item == 1) {
ret++;
clearIsland(index, indey);
}
}
}
return ret;
};
```
hash+递归直接秒
https://leetcode.cn/problems/path-sum-iii/submissions/561336523/?envType=study-plan-v2&envId=top-100-liked
```js
var pathSum = function (root, targetSum) {
const map = new Map();
map.set(0,1)
let ret = 0;
let presum = 0;
const dfs = (root) => {
if(root==null){
return
}
const haveNum =presum- (targetSum - root.val);
if (map.has(haveNum)) {
ret += map.get(haveNum);
}
presum += root.val;
if (map.has(presum)) {
map.set(presum, map.get(presum) + 1);
} else {
map.set(presum, 1);
}
dfs(root.left);
dfs(root.right);
map.set(presum, map.get(presum) - 1);
presum -= root.val;
};
dfs(root);
return ret;
};
```
嫖到的一个二叉树建立的辅助函数
```js
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function buildTree(arr) {
if (!arr.length) return null;
let root = new TreeNode(arr);
let queue = ;
let i = 1;
while (i < arr.length) {
let current = queue.shift();
if (arr !== null) {
current.left = new TreeNode(arr);
queue.push(current.left);
}
i++;
if (i < arr.length && arr !== null) {
current.right = new TreeNode(arr);
queue.push(current.right);
}
i++;
}
return root;
}
```
橘子问题，利用数组秒
```js
/**
* @param {number[][]} grid
* @Return {number}
*/
var orangesRotting = function (grid) {
let decayArr = [];
let total = 0;
for (let index = 0; index < grid.length; index++) {
for (let indey = 0; indey < grid.length; indey++) {
if (grid == 2) {
decayArr.push({ index, indey });
total++;
}
if (grid == 1) {
total++;
}
}
}
let minues = -1;
let noFind = true;
const decay = (x, y) => {
const position = [
,
,
,
,
];
for (let index = 0; index < position.length; index++) {
const pos = position;
const x = pos;
const y = pos;
if (x < 0 || x >= grid.length) {
continue;
}
if (y < 0 || y >= grid.length) {
continue;
}
if (grid]] == 1) {
grid]] = 2;
decayArr.push({
index: x,
indey: y,
});
noFind = false;
}
}
};
do {
minues++;
noFind = true;
const cycle = [...decayArr];
for (let index = 0; index < cycle.length; index++) {
const orange = decayArr;
decay(orange.index, orange.indey);
}
} while (noFind == false);
return total==decayArr.length? minues:-1;
};
```
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/562017729/?envType=study-plan-v2&envId=top-100-liked
边界没扣明白，看了一下答案
```js
var lowestCommonAncestor = function (root, p, q) {
let result = undefined
const dfs = (root) => {
if(root==null){
return false
}
const left = dfs(root.left);
const right = dfs(root.right);
if (left && right) {
result = result ?? root
}
if ((left || right) && ((root == p) || (root == q))) {
result = result ?? root
}
return left || right || (root == p) || (root == q)
}
dfs(root)
return result
};
```
https://leetcode.cn/problems/binary-tree-maximum-path-sum/submissions/562017878/?envType=study-plan-v2&envId=top-100-liked
递归题，扫了一眼答案
```js
var maxPathSum = function (root) {
let max = Number.MIN_SAFE_INTEGER
const dfs = (node) => {
if (node == null) {
return 0
}
let left = Math.max(dfs(node.left), 0)
let right = Math.max(dfs(node.right), 0)
max=Math.max(max,left+right+node.val)
return Math.max(Math.max(left, right) + node.val, 0)
}
dfs(root)
return max
};
```