日期: 2021 年 6 月 8 日

114. 二叉树展开为链表（JS实现）

1 题目
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/
2 5
/ \
3 4 6
将其展开为：
1

2

3

4

5

6

2 思路
这道题我的思路比较直接，首先前序遍历树，然后用next指针链接每个节点，随后修改原来right指针，题解的方法比较巧妙，对树进行变形的后序遍历，遍历顺序是右子树->左子树->根节点
例如，我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点，6 <- 5 <- 4 3 2 1

1
/ \
2 5
/ \ \
3 4 6
1
2
3
4
5
3代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
const stack = [];
let p = root;
let link = {};
let linkHead = link;

while (p || stack.length > 0) {
while (p) {
link.next = p;
link = link.next;
stack.push(p);
p = p.left;
}

p = stack.pop();
p = p.right;
}

link = linkHead.next;
while(link) {
root.right = link.next;
root.left = null;
root = root.right;
link = link.next;
}
};

ios md5加密
#import <CommonCrypto/CommonDigest.h>

+ (NSString *)md5:(NSString *)string {
const char *cStr = [string UTF8String];
unsigned char digest[CC_MD5_DIGEST_LENGTH];
CC_MD5(cStr, (CC_LONG)strlen(cStr), digest);
NSMutableString *result = [NSMutableString stringWithCapacity:CC_MD5_DIGEST_LENGTH * 2];
for (int i = 0; i < CC_MD5_DIGEST_LENGTH; i++) {
[result appendFormat:@”%02X”, digest[i]];
}
return result;
}

填充每个节点的下一个右侧节点指针（JS实现）

1 题目
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”1″,”left”:{“id”:“2”,“left”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:4}̲,”next”:null,”r…id”:“4”,“left”:null,“next”:null,“right”:null,“val”:5},“val”:2},“next”:null,“right”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”5″,”left”:{“id”:“6”,“left”:null,“next”:null,“right”:null,“val”:6},“next”:null,“right”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:7}̲,”val”:3},”val”…id”:“1”,“left”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”2″,”left”:{“id”:“3”,“left”:null,“next”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …:null,”next”:{“id”:“5”,“left”:null,“next”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:7}̲,”right”:null,”…id”:“7”,“left”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 9: ref”:”5″}̲,”next”:null,”r…ref”:“6”},“val”:3},“right”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 9: ref”:”4″}̲,”val”:2},”next…ref”:“7”},“val”:1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

2 思路
这道题的主要思路是使用层序遍历的方法，逐层遍历节点，并连接相邻的节点， 题解比较巧妙，为了只使用O(1)的额外空间，其在层序遍历时，即连接当前节点的左右子节点，通过next指针链接兄弟节点的子节点

3代码
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/

/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
let queue = [root];
let temp = [];
let p, pre = root;

while (queue.length > 0 || temp.length > 0) {
if (queue.length === 0) {
queue = temp;
temp = [];
pre.next = null;
pre = null;
}
p = queue.shift();
if (!p) continue;
temp.push(p.left);
temp.push(p.right);

if (!pre) {
pre = p;
} else {
pre.next = p;
pre = p;
}
}

return root;
};

路径总和（JS实现）

1 题目
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

2 思路
这道题的主要思路是使用递归的方法将从根节点到达每个叶子节点的路径和都保存起来，然后查找有没有目标值，要注意根节点没有左右孩子的特殊情况

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
const values = [];

function d(p, value) {
if (!p) return false;

if (!p.left && !p.right) {
values.push(value + p.val);
return;
}

d(p.left, value + p.val);
d(p.right, value + p.val);
}

if (!root) return false;

if (!root.left && !root.right) return sum === root.val;

if (!root.left) {
d(root.right, root.val);
} else if (!root.right) {
d(root.left, root.val);
} else {
d(root, 0);
}

return values.includes(sum);
};

二叉树展开为链表（JS实现）

1 题目
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/
2 5
/ \
3 4 6
将其展开为：
1

2

3

4

5

6

2 思路
这道题我的思路比较直接，首先前序遍历树，然后用next指针链接每个节点，随后修改原来right指针，题解的方法比较巧妙，对树进行变形的后序遍历，遍历顺序是右子树->左子树->根节点
例如，我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点，6 <- 5 <- 4 3 2 1

1
/ \
2 5
/ \ \
3 4 6

3代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
const stack = [];
let p = root;
let link = {};
let linkHead = link;

while (p || stack.length > 0) {
while (p) {
link.next = p;
link = link.next;
stack.push(p);
p = p.left;
}

p = stack.pop();
p = p.right;
}

link = linkHead.next;
while(link) {
root.right = link.next;
root.left = null;
root = root.right;
link = link.next;
}
};

填充每个节点的下一个右侧节点指针（JS实现）

1 题目
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”1″,”left”:{“id”:“2”,“left”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:4}̲,”next”:null,”r…id”:“4”,“left”:null,“next”:null,“right”:null,“val”:5},“val”:2},“next”:null,“right”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”5″,”left”:{“id”:“6”,“left”:null,“next”:null,“right”:null,“val”:6},“next”:null,“right”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:7}̲,”val”:3},”val”…id”:“1”,“left”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …”:”2″,”left”:{“id”:“3”,“left”:null,“next”:{“KaTeX parse error: Expected ‘}’, got ‘EOF’ at end of input: …:null,”next”:{“id”:“5”,“left”:null,“next”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 53: …t”:null,”val”:7}̲,”right”:null,”…id”:“7”,“left”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 9: ref”:”5″}̲,”next”:null,”r…ref”:“6”},“val”:3},“right”:{“KaTeX parse error: Expected ‘EOF’, got ‘}’ at position 9: ref”:”4″}̲,”val”:2},”next…ref”:“7”},“val”:1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

2 思路
这道题的主要思路是使用层序遍历的方法，逐层遍历节点，并连接相邻的节点， 题解比较巧妙，为了只使用O(1)的额外空间，其在层序遍历时，即连接当前节点的左右子节点，通过next指针链接兄弟节点的子节点

3代码
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/

/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
let queue = [root];
let temp = [];
let p, pre = root;

while (queue.length > 0 || temp.length > 0) {
if (queue.length === 0) {
queue = temp;
temp = [];
pre.next = null;
pre = null;
}
p = queue.shift();
if (!p) continue;
temp.push(p.left);
temp.push(p.right);

if (!pre) {
pre = p;
} else {
pre.next = p;
pre = p;
}
}

return root;
};

填充每个节点的下一个右侧节点指针 II（JS实现）

1 题目
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
树中的节点数小于 6000
-100 <= node.val <= 100

2 思路
这道题的主要思路在层序遍历每个节点时，逐步连接子节点

3代码
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/

/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
let p = root;
let next = null;
let leftMost;

while (p) {
while(p) {
next = p.next;
while (next && !next.left && !next.right) { //寻找下一个具有子节点的兄弟节点
next = next.next;
}
connect(p, next); //连接相邻的两个兄弟节点
p = next;
}

p = leftMost; //跳转到下一层
leftMost = null;
}

function connect(p, nextNode) {
if (!p.left && !p.right) return; //如果当前节点无子节点，那么无需连接后续节点

if (!leftMost) leftMost = p.left || p.right; //记录当层*左端的节点

if (p.left && p.right) { //如果当前节点有两个子节点，先将两个子节点连接在一起
p.left.next = p.right;
}

let linkNode = p.right || p.left; //找到当前节点靠右的子节点

if (nextNode) { //将当前节点靠右的子节点和当前节点兄弟节点的子节点连接在一起
linkNode.next = nextNode.left || nextNode.right;
} else {
linkNode.next = null;
}
}

return root;
};

三角形*小路径和（JS实现）

1 题目
给定一个三角形，找出自顶向下的*小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的*小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

2 思路
这道题的主要思路用一个数组d来存储每层每个数的*小路径和，其中d[i]代表某层经过第i个数的*小路径和，下一层比上一层总是多一个数，因此除首尾两个数外，状态转移方程为dNext[i] = Math.min(d[i-1], d[i]) + arr[i]

3代码
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
if (triangle.length === 0) return 0;
if (triangle.length === 1) return triangle[0][0];

let d = [triangle[0][0]];
let m = triangle.length;

for (let i=1; i<m; i++) {
let temp = [];
let arr = triangle[i];
let len = arr.length;
temp[0] = d[0] + arr[0]; //首尾两个数直接加上就好
temp[len- 1] = d[d.length-1] + arr[len – 1];
for (let j=1; j<len-1; j++) {
temp[j] = Math.min(d[j-1], d[j]) + arr[j];
}
d = temp;
}

return Math.min(…d);
};

多级菜单和滚动条共存overflow问题

前天，在学习中遇到一个问题，要实现一个多级菜单，且每级菜单都有滚动条，这时我想使ul元素overflow-x为visible，而overflow-y为auto，但发现设置以后并没有按照想像中的生效，x和y方向都变为了auto，*后发现是CSS规范这样限制的

“ overflow-x”和“ overflow-y”的计算值与它们的指定值相同，除了不可能与“ visible”进行某些组合：如果将一个指定为“ visible”而另一个指定为“ scroll”或“自动”，然后将“可见”设置为“自动”

*后参考这篇文章解决了问题 https://css-tricks.com/popping-hidden-overflow/

买卖股票的*佳时机（JS实现）

1 题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你*多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的*大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，*大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以*大利润为 0。

2 思路
leecode上的股票题一共有6道，均使用动态规划的思路来解决，看题解里面这篇文章讲的很不错，总体上做这类题的步骤是：列举所有状态 -> 推导状态转移方程 -> 解决问题

3代码
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let maxProfit = 0;
let minPrice = prices[0];

for (let i=1; i<prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] – minPrice);
}
}

return maxProfit;
};