注释
在前端中的确用到不少与树相干的的常识，比方说 DOM 树，Diff 算法，包含原型链其实都算是树，学会树，其实对于学这些常识还是有比拟大的帮忙的，当然咱们学算法还是得思考面试，而树恰好也是一个大重点 — 起码在前端而言；
次要起因在于，树它金玉其外; 败絮其中，比拟下里巴人，须要形象然而又能把图画进去不至于让你毫无脉络，简略而言就是看上去很厉害，但实际上也很接地气，俗称 比拟个别；要晓得做前端的面试算法，考的不就是你有么得被动学习能力，形象能力等，然而思考到参差不齐的前端娱乐圈，考得难吧可能就全是漏网之鱼了，所以既要筛选出鱼，然而又不能难度过大，树就是那个比拟适中的，所以连忙刷起来吧敌人们；
这里原本是要遵循 3:5:2 难度来刷，预计刷个 30 题就差不多，然而理论中等题刷得骑虎难下，难题是欲仙欲死，容易题是味如嚼蜡，所以 XDM 担待一下。选题次要是那个男人精选的例题以及 Leetcode 中 HOT 题和字节专题，总的来说代表性还是够的，刷完应该大略或者可能应酬一下树这方面的算法了。
如果感觉有那么点帮忙，请点个赞留个言，点赞超过 10 个就更新下一 part；好吧，即使不过也会更新，就是这么臭不要脸，大家伙加油吧，欧力给！！
二叉树的遍历
递归遍历
- 递归的时候前中后序都能间接解决完了
- 递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了
迭代遍历 — 双色标记法
- 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 — 能够用数字或者其余任意标签标示
- 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 — 中序遍历
- 如果遇到的节点是灰色的，则将节点输入
- 留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 – 中 – 右，那么在插入栈的时候要反过来 右 – 中 – 左
依照那个男人的批示，失常咱们就用递归做就好，就如同咱们做非排序题排序的时候，sort 一下就好了，然而一旦面试官问到用另外的迭代形式的时候，咱们再套个模板，会比记住多个迭代写法要简略，毕竟内存容量无限，而后续遍历的迭代写法的确挺坑的，能省一点内存就省一点吧
144. 二叉树的前序遍历
// 144. 二叉树的前序遍历
/** * @剖析 -- 递归 */
var preorderTraversal = function (root) {const ret = [];
const recursion = (root) => {if (!root) return;
ret.push(root.val);
recursion(root.left);
recursion(root.right);
};
recursion(root);
return ret;
};
/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，这里是前序遍历，中 - 左 - 右，那么在插入栈的时候要反过来 右 - 左 - 中 */
var preorderTraversal = function (root) {const ret = [];
const stack = [];
stack.push([root, 0]); // 0 是红色未解决的，1 是灰色解决过的
while (stack.length) {const [root, color] = stack.pop();
if (root) {if (color === 0) {
// 遇到白球，则插入 -- 前序
stack.push([root.right, 0]);
stack.push([root.left, 0]);
stack.push([root, 1]);
} else {
// 遇到灰球，则收网
ret.push(root.val);
}
}
}
return ret;
};
1.94 二叉树的中序遍历
// 94. 二叉树的中序遍历
/** * @剖析 * 1. 递归的时候前中后序都能间接解决完了 * 2. 递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了 */
var inorderTraversal = function(root) {const ret = []
const recursion = root => {if(!root) return
recursion(root.left)
// 这里是中序，所以在两个递归之间，如果是前序就在后面，后序就在前面
ret.push(root.val)
recursion(root.right)
}
recursion(root)
return ret
};
/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右，那么在插入栈的时候要反过来 右 - 中 - 左 */
var inorderTraversal = function(root) {const ret = []
const stack = []
stack.push([root,0]) // 0 是红色未解决的，1 是灰色解决过的
while(stack.length) {const [root,color] = stack.pop()
if(root){if(color === 0){
// 遇到白球，则插入 -- 中序遍历
stack.push([root.right,0])
stack.push([root,1])
stack.push([root.left,0])
}else{
// 遇到灰球，则收网
ret.push(root.val)
}
}
}
return ret
};
145. 二叉树的后序遍历
// 145. 二叉树的后序遍历
/** * @剖析 -- 递归 */
var postorderTraversal = function(root) {const ret = []
const dfs = (root) => {if(!root) return
dfs(root.left)
dfs(root.right)
ret.push(root.val)
}
dfs(root)
return ret
};
/** * @剖析 -- 迭代 -- 双色球 */
var postorderTraversal = function(root) {const ret = []
const stack = []
stack.push([root,0])
while(stack.length){const [root,color] = stack.pop()
if(root) {if(color === 0){stack.push([root,1])
stack.push([root.right,0])
stack.push([root.left,0])
}else{ret.push(root.val)
}
}
}
return ret
}
刷题过程一些纳闷点
自顶向下 (前序遍历) 和自低向上(后续遍历)
这两个名词在很多讲树的题解中常常会呈现，而这与咱们遍历树求值到底关联点在哪里，缓缓刷题之后我发现，尽管 dfs 有三种模式，但在形象到具体题目的时候，其实是属于不同的办法的。
对于 前序遍历 而言，就是先获取到根节点的信息，而后做了肯定编码后，再向下遍历，这种遍历形式就是所谓的 自顶向下 的思维，咱们从根节点开始，能够携带肯定的信息，再持续往下遍历时，先解决，失去临时性后果，给顶层的节点作为信息；
对于 自顶向下 的遍历而已，遍历到根节点，就解决完结所有的节点，也相应的失去预期后果了，所以个别应用 前序遍历 办法解题的，都会申明一个全局变量，而后遍历完之后，返回这个值.
例子:563. 二叉树的坡度
剖析
1. 自底向上返回子树值之和，而后求出对应的坡度，累加起来即可.
2. 须要留神的是，左右子树的累加值大小不确定，须要用绝对值
3. 工夫复杂度 ${O(N)}$
var findTilt = function (root) {
let ret = 0;
const recursion = (root) => {if (!root) return 0;
const left = recursion(root.left);
const right = recursion(root.right);
ret += Math.abs(left - right);
return left + right + root.val;
};
recursion(root);
return ret;
};
对于 后序遍历 而言，是想遍历到叶子节点，而后再向下来解决根节点，也就是所谓的 自底向上；
实际上，自底向上 是一种递归的办法，先 递 到叶子节点，解决完返回肯定的值，再 归回来，后续的解决都是依据子树的值作为入参的，所以不要被 遍历 蛊惑， 后续遍历 可不是遍历完就完结了，那才刚刚开始呢。
所以前面为了辨别，在解决 自底向上 题目的时候，函数名字都不再应用 dfs，而是间接应用 recursion；
参考视频：传送门
例子:
判断遍历到边界，什么在叶子节点处判断，什么时候间接跑到 null 返回？
先来解释一下，在做 dfs 遍历的时候，咱们须要遍历到叶子节点，而后做最终的解决，有的题目咱们看到的是判 null 时返回 null/0 等；有的时候咱们直接判断是否叶子节点，if(!root.left && !root.right)；
这是在刷题过程中感觉忒蛊惑的中央，在最开始的时候，我喜爱应用 null，因为它写的更少，而且顺便把根节点为空的边界也做了，最近刷的时候我开始感觉 判断节点 会更稳当一点，而且不必做更深的解决，直到我再写👆下面的文字时，有那么一点想法
在咱们应用 自底向上 的时候，因为须要从子节点中 return 值，这个时候即使是 null 也是 有用 的，所以应用 null 根本是 OK 的。
例子: 104. 二叉树的最大深度
/** * 1. 自顶向下，带个层数参数，断定为叶子节点就进行最大值判断 */
var maxDepth = function (root) {if (!root) return 0;
let ret = 0;
const dfs = (root, depth) => {if (root.left) dfs(root.left, depth + 1);
if (root.right) dfs(root.right, depth + 1);
ret = Math.max(ret, depth);
return;
};
dfs(root, 1);
return ret;
};
// 自低向上
var maxDepth = function (root) {const dfs = (root) => {if (!root) return 0;
return Math.max(dfs(root.left), dfs(root.right))+1;
};
return dfs(root);
};
而在一些携带数据，自顶向下 求值的题目中，如果跑到 null 才完结遍历，就比拟容易呈现反复计算的谬误，而且因为不须要获取 return 值，这个时候我倡议是应用 判断节点 的办法。
例子:1022. 从根到叶的二进制数之和
/** * @剖析 * 1. 自顶向下求出每一条路以后对应的数字，保留在入参中 * 2. 在叶子节点处将值累加起来即可 * 3. 须要留神的是，要在叶子节点就解决，而不是在 null 的时候解决，不然会反复计算 */
var sumRootToLeaf = function(root) {// if(!root) return 0 // 题目已知节点是 1-1000
let ret = 0
const dfs = (root,sum) => {const temp = (sum<<1) + root.val
if(!root.left && !root.right){
ret +=temp
return
}
if(root.left) dfs(root.left,temp)
if(root.right) dfs(root.right,temp)
}
dfs(root,0)
return ret
};
简略题
101. 对称二叉树
剖析
- 对称二叉树，其实是要求是否镜像对齐，所以递归过程至多须要两个根节点，而后 dfs 次要就是判断是否是对称的两棵树
- 这里是自顶向下调配互相比拟的子树节点 left 和 right，而后再自底向上的返回最终后果
- 在某一次 dfs 中，如果比拟单方都是 null，那么证实比拟单方是对称的；如果呈现只有一方有值，或者单方有值然而值不一样的时候，返回 false；
- 每次递归都是左右外层形成比拟，左右内层形成比拟
- 工夫复杂度: O(h), 其中 h 是树的高度
// 101. 对称二叉树
var isSymmetric = function (root) {if (!root) return false;
const dfs = (left, right) => {if (!left && !right) return true;
if (!left || !right || left.val !== right.val) return false;
return dfs(left.left, right.right) && dfs(left.right, right.left);
};
return dfs(root.left, root.right);
};
104. 二叉树的最大深度
- 应用树的三种搜寻形式，层序，自顶向下的 dfs，自底向上的递归 dfs
层序遍历
- 无论是深度，层数等，间接用层序遍历找到最初一层的最初一个叶子节点即可
- 工夫复杂度 O(N), 空间复杂度 O(K) — K 是最大宽度
// 104. 二叉树的最大深度
/** * 1. 无论是深度，层数等，间接用层序遍历找到最初一层的最初一个叶子节点即可 */
var maxDepth = function (root) {if (!root) return 0;
let ret = 0;
const queue = [];
queue.push(root);
while (queue.length) {
ret++; // 进入一层
let len = queue.length;
while (len--) {
// 层序遍历
const root = queue.shift();
if (root.left) queue.push(root.left);
if (root.right) queue.push(root.right);
}
}
return ret;
};
dfs — 自顶向下
- 咱们在计算层数的时候，能够思考到，没遍历一层，就携带一个参数，这个参数是一个标记，比如这里就是深度 depth
- 这样当咱们遍历到叶子节点的时候，都能够和最大值比对一下，而后完结这一条路线
- 工夫复杂度 O(N), 空间复杂度 O(D) — D 是深度
/** * 1. 自顶向上，带个层数参数，断定为叶子节点就进行最大值判断 */
var maxDepth = function (root) {if (!root) return 0;
let ret = 0;
const dfs = (root, depth) => {if (root.left) dfs(root.left, depth + 1);
if (root.right) dfs(root.right, depth + 1);
// 走到这的时候，证实是叶子节点了，所以取最大值，就完结这一次的
ret = Math.max(ret, depth);
};
dfs(root, 1);
return ret;
};
递归 — 自低向上
- 既然有自顶向下，那么当然就有自低向上了；
- 就我肤浅的算法能力而已，自顶向下就是带参数的深度优先遍历 DFS, 而自低向上，是递归，须要 dfs 到了底部，而后归到根节点，所以这里用的是 recursion 作为办法名。
- 自顶向下是从根节点开始算一层深度，而后跑到叶子节点完结；自低向上反过来，跑到最底层，而后一直求叶子结点的最大深度，然加上本身返回到下层
- 工夫复杂度 O(N), 空间复杂度 O(1)
// 自低向上
var maxDepth = function (root) {const recursion = (root) => {
// 只是到了底部，所以高度为 0
if (!root) return 0;
// 每一个节点的高度是多少，就是两个节点树的最大高度 + 本人所处的这一层 1
return Math.max(recursion(root.left), recursion(root.right)) + 1;
};
return recursion(root);
};
226. 翻转二叉树
剖析 — 自底向上
- 因为要求的是反转二叉树，对于任意一颗子树，其实都是要做一样的操作，所以能够先递到叶子节点，而后开始进行翻转
- 自底向上将翻转好的子树传递到下层的节点，直到最初的根节点，失去了两课翻转好的树，而后替换一下一下地位就好了
- 工夫复杂度 O(N)
// 226. 翻转二叉树
var invertTree = function (root) {const dfs = (root) => {
// 达到了最底部，间接返回 null
if (!root) return null;
// 1. 递归获取翻转后的左右子树
const left = dfs(root.left);
const right = dfs(root.right);
// 2. 反转两棵树的地位
root.left = right;
root.right = left;
// 最初返回这个反转之后的树
return root;
};
return dfs(root);
};
563. 二叉树的坡度
剖析
- 自底向上返回子树值之和，而后求出对应的坡度，累加起来即可.
- 须要留神的是，左右子树的累加值大小不确定，须要用绝对值
- 工夫复杂度 O(N)
var findTilt = function (root) {
let ret = 0;
const recursion = (root) => {if (!root) return 0;
const left = recursion(root.left);
const right = recursion(root.right);
ret += Math.abs(left - right);
return left + right + root.val;
};
recursion(root);
return ret;
};
1022. 从根到叶的二进制数之和
剖析
- 自顶向下求出每一条路以后对应的数字，保留在入参中
- 在叶子节点处将值累加起来即可
- 须要留神的是，要在叶子节点就解决，而不是在 null 的时候解决，不然会反复计算
var sumRootToLeaf = function(root) {// if(!root) return 0 // 题目已知节点是 1-1000
let ret = 0
const dfs = (root,sum) => {const temp = (sum<<1) + root.val
if(!root.left && !root.right){
ret +=temp
return
}
if(root.left) dfs(root.left,temp)
if(root.right) dfs(root.right,temp)
}
dfs(root,0)
return ret
};
783. 二叉搜寻树节点最小间隔
剖析
- 这是一课二叉搜寻树 BST , 间接拍脑袋想用中序遍历，失去的值是单增的
- 应用一个变量保留 BST 中序遍历过程中的第一个值；应用一个全局变量保留最小的差值
- 工夫复杂度 O(N)
var minDiffInBST = function(root) {
let ret = Infinity
let prev = undefined // 保留上一个值
const dfs = (root) => {if(!root) return
dfs(root.left)
// 在这里解决
if(prev === undefined){
// 第一个值，因为差值须要两个值，所以这相当于初始化了
prev = root.val
}else{ret = Math.min(ret,root.val-prev)
prev = root.val
}
dfs(root.right)
}
dfs(root)
return ret
};
中等题
662. 二叉树最大宽度
剖析 — 基于齐全二叉树的个性
- 求宽度，盲猜用层序遍历比拟适合，然而啥时候加 null 是个体面活
- 这里有一个降难度的点 — 该层最左和最右的非空节点，两端点间的 null 节点也计入长度 — 也就是在遍历存在节点的一层时，第一个节点必定是存在，最初一个节点也是
- 尽管左侧节点确定了，然而右侧节点大小不确定啊，两头存在有多少个 null，前面是否存在一个节点隔开了 n 个 null 都不确定，这个时候能够思考把树当成是齐全二叉树，而后所有的节点再带一个 pos 属性
- 咱们以 1 作为根节点 root 的 pos，左节点就是 2n, 右节点是 2n+1
- 留神，因为节点 pos 的值是出现指数级别回升的，即 2^k, 其中 k 是树的深度，咱们又晓得当 2^53 之后，精度会失落，
- 所以坑爹的就是，输出能够是先右树走 1 个节点 53 次，而后第 54 层开始来实在值，酱紫后面 53 层的宽度都是 1，从 54 层开始须要开始计算，然而这个时候，pos 曾经超出 JS 的 Number 类型的计算极限了
- 这个时候咱们思考应用 js 的新的根本类型 BigInt 作为节点 pos 的值，然而又因为数字类型和大数类型之间是不能进行运算的，所以最初求值的时候，要进行响相应的转换。
// 662. 二叉树最大宽度
var widthOfBinaryTree = function (root) {const queue = [];
queue.push([root, 1n]);
let max = 0;
let steps = 0,
curDepth = 0; // 这是用来确定第一个节点的
let leftPos = 0n; // 每一次左侧节点的地位
while (queue.length) {
// 层数 +1
steps++;
// 如果还有层
let len = queue.length;
while (len--) {
// 开始一层的遍历了
const [root, pos] = queue.shift(); // 取出节点
if (root) {
// 只有有子节点，那么即使有一个不存在，也得放到队列中
queue.push([root.left, 2n * pos]);
queue.push([root.right, 2n * pos + 1n]);
if (curDepth !== steps) {
// 第一个节点
curDepth = steps; // 这个时候更新一下深度
leftPos = pos; // 左侧节点的地位
}
// 每一个存在的节点，都会一直进行更新
// 因为 bigInt 和 number 是不能进行数学运算的，所以先将 bigint 转成字符串类型，而后隐式转成数字，而后进行比拟
max = Math.max(max, (pos - leftPos + 1n).toString());
}
}
}
return max;
};
971. 翻转二叉树以匹配先序遍历
剖析:
- 我感觉本题最大的难点是读题，了解题意，首先对于树的翻转概念，能够先去一道简略题 226. 翻转二叉树 理解一下。
- 这里的翻转波及到的是根节点是否要翻转左右树，所以在遍历过程中，必定是以根节点作为入参，而后进行一系列逻辑的，毕竟如果须要翻转的时候，ret 要存的是根节点
- 这里给出了一个待操作的树 A 的根节点 root，和树 V 先序遍历的数组，而后求的是 A 是否翻转起码的 n 个节点，使得 A 和 V 统一。OK，当初其实就是开始前序遍历树 V，而后用 V 的值去匹配 A，看看是否进行树的匹配
- 对于一次遍历，咱们首先判断根节点的值是统一，才会进入这一次的遍历中，而后次要是看左右树，对于树 V 来说，用 pos 一直依照先序遍历给出值，而对于 V 来说，你能够用左树匹配，如果匹配胜利，则啥事没有，大家是一样的；而如果左树不匹配，用右树后行，而后再走左树，这种状况就须要翻转一下以后的节点，保障树 A 要在前序遍历的状况和 V 匹配；
- 如果在匹配过程中 A 的左右树都没有匹配胜利，则会提取走出 A 的遍历，这个时候 pos 就没有迭代完，这个时候就是异样，返回 [-1]
- 工夫复杂度 O(N)
var flipMatchVoyage = function(root, voyage) {if(root.val !== voyage[0]) return [-1] // 用来在进入 dfs 前对根节点的判断
const ret = []
let pos = 0 // 这是用来获取 voyage 值，也是遍历树 V 的，如果没有走完，证实无奈匹配 root
const dfs = root => {
// 每一次的遍历 pos 都要跟随着
pos++
// 对于每一个节点，都是依照先序遍历的写法
if(root.left && root.left.val === voyage[pos] ){
// 如果在这节点左树适配，那就持续走，因为这是先序遍历
dfs(root.left)
}
if(root.right && root.right.val === voyage[pos] ){dfs(root.right)
// 右树实现之后，须要看看当初 pos 所在的值是否能够匹配左树，即是否先走右树再走左树，成立即以后的 root 节点就是须要进行翻转的节点
if(root.left && root.left.val === voyage[pos] ){ret.push(root.val)
dfs(root.left)
}
}
}
dfs(root)
if(pos<voyage.length){
// voyage 还没有走完，就被限度条件卡住了
return [-1]
}
return ret
};
863. 二叉树中所有间隔为 K 的结点
剖析
- 简略合成一下，如果题目改成
找到间隔根节点 K 的节点，是不是一下就能够找到，从根节点登程，走 K 步就好了 - 在略微延长一下，
找出间隔节点 target K 的子节点，那么也一样，就是只能从子节点中去找，这道题之所以能成为 medium，就是因为它的 target 不肯定是根节点，同时它能够往下来找； - 对于简略的二叉树，是没法子依据子节点找打它的父节点的，就如同单向链表无奈依据 current 节点找到上一个节点 prev 一样，那么咱们能够本人造一个，想想经典的 diff 算法，很多时候咱们在用树的时候，都须要间接找到父节点的，所以这里第一步就是为 root 到 target 节点造指针 parent
- 在正式开始寻找的时候，须要留神的时候，当咱们从底往上找父节点作为根节点，而后再自顶向下找子节点的过程，会有反复取值的危险，所以须要有一个变量存储向上取父节点时的节点，而后再每一次想下找值的时候，避开这些节点
var distanceK = function (root, target, k) {
let targetNode = undefined;
// 第一个 dfs，是为了在 根节点 -> target 之间的的节点打上 parent 的指针，不便从下往上找
const setDfs = (root) => {if (root === target) {
// 找到了, 就让剩下的搜寻进行
targetNode = root;
}
if (root.left && !targetNode) {
root.left.parent = root;
setDfs(root.left);
}
if (root.right && !targetNode) {
root.right.parent = root;
setDfs(root.right);
}
};
setDfs(root);
const ret = [];
const paths = []; // 向上取父节点时，走过节点
// 从上往上来找, 其中 index 示意间隔 target 的间隔
const find = (root, index) => {if (index === k) {ret.push(root.val);
}
if (index < k) {if (root.left && !paths[root.left.val]) find(root.left, index + 1);
if (root.right && !paths[root.right.val]) find(root.right, index + 1);
}
};
let index = 0;
while (targetNode && index <= k) {
// 记录向上取的父节点
paths[targetNode.val] = targetNode.val;
// 从根节点向下求取适合的值
find(targetNode, index);
targetNode = targetNode.parent;
// 每网上一次，就要将节点走一次
index++;
}
return ret;
};
面试题 04.06. 后继者
剖析
- 依据中序遍历，将所有的节点都保留到数组中，而后找到 P 的时候，保留下一个值的下标，而后遍历完结后，从数组中取即可
- 工夫和空间复杂度都是 O(N)
var inorderSuccessor = function(root, p) {if(!root) return null
let arr = []
let ret = 0
const dfs = (root) => {if(!root) return
dfs(root.left)
arr.push(root)
if(root === p) {ret = arr.length}
dfs(root.right)
}
dfs(root)
return arr[ret] || null
};
98. 验证二叉搜寻树
剖析
- 二叉搜寻树的特色: 根节点大于左节点，小于右节点
- 前序遍历过程中，是单增的过程；
- 咱们不须要保护一个数组，只须要保护上一个值做大小判断就好
- 所以前序遍历过程中，而后和一个全局遍历进行大小比拟即可；
var isValidBST = function(root) {if(!root) return false
let pre = -Infinity // 最小值
let ret = true // 默认就是
const inorder = (root) => {if(root.left && ret) inorder(root.left)
if(root.val<=pre) {
ret = false // 一旦有一组失败，都不是 BST
return
}else {pre = root.val}
if(root.right && ret) inorder(root.right)
}
inorder(root)
return ret
};
99. 复原二叉搜寻树
剖析
- 既然提醒应用 O(N) 空间复杂度很容易实现，那就是如果间接用数组保留中序遍历的数组，失去后果比较简单，所以咱们就来一下暴力解法
- 先中序遍历失去一个节点数组
- 这个数组的值必定不是单增的，那么就是存在两个值和排序后不一样，所以另开一个数组存储值，排序后，再比对，而后扭转节点的对应的值
- 工夫复杂度 O(nlogn), 空间复杂度 O(N)
// 暴力法 -- 空间复杂度为 ${O(N)}$
var recoverTree = function(root) {const ret = []
const dfs = (root) => {if(!root) return
dfs(root.left)
ret.push(root)
dfs(root.right)
}
dfs(root);
// 挪动两个值，使得数组 ret 单增
// 另开一个数组 ret2，排序
let sorted = ret.map(item => item.val)
sorted.sort((a,b)=> a-b)
sorted.forEach((sorted,index) => {if(sorted !== ret[index].val) {ret[index].val = sorted
}
})
};
222. 齐全二叉树的节点个数
间接遍历一次就能够失去节点的数量
var countNodes = function(root) {
let ret = 0
const preorder = root => {if(!root) return
ret++
preorder(root.left)
preorder(root.right)
}
preorder(root)
return ret
};
面试题 04.12. 求和门路
剖析 — 双 dfs
- 起始点不限度，然而门路必须是向下，也就不能倒转网上走
- 两个 dfs，一个指向起始节点，一个以起始节点为根节点往下找
- 留神 1：这里的值是任意值，所以不能用超出值或者取到门路就接续 dfs，而是必须要扫到叶子节点
- 工夫复杂度 O(NlogN) 相当于树中的每一个节点都当了初始节点，而后去遍历子树(find)
var pathSum = function (root, sum) {
let ret = 0;
// 遍历节点的 dfs
const dfs = (root) => {if (!root) return;
find(root, 0);
dfs(root.left);
dfs(root.right);
};
const find = (root, total) => {
total += root;
// if (total > sum) return; // 完结这跳线 -- 这里
if (total === sum) {
// 符合条件
ret++;
// return;
}
if (root.left) find(root.left, total);
if (root.right) find(root.right, total);
};
dfs(root);
return ret;
};
129. 求根节点到叶节点数字之和
剖析：
- 这里理论考查的就是按要求从根节点走到叶子节点，而所谓的数字相加只是一种模式
- 显然应用前序遍历，每一次先解决根节点的值，而后再解决左右节点的值，合乎题意
- 工夫复杂度 O(N)
var sumNumbers = function (root) {
let ret = 0
const dfs = (root,num) => {
let cur = num*10+root.val
if(!root.left && !root.right) {
// 叶子节点 -- 这里判断有节点才走，次要是为了找到叶子节点，而不是到叶子结点下的 null，这样会反复计算
ret+=cur
}
if(root.left) dfs(root.left,cur)
if(root.right) dfs(root.right,cur)
}
dfs(root,0)
return ret
}
1448. 统计二叉树中好节点的数目
剖析
- 将题目转化，在前序遍历过程中，保护一个最大值，如果在整条门路中的最大值小于等于以后节点的值，那么这个节点就是号节点
- 只有是好节点的时候，才须要替换最大值，而后遍历完就能够找出所有的号节点
- 工夫复杂度 O(N)
var goodNodes = function(root) {
let ret = 0
const dfs = (root,max) => {if(root.val>=max) {
ret++
max = ret
}
if(root.left) dfs(root.left,max)
if(root.right) dfs(root.right,max)
}
dfs(root,-Infinity)
return ret
};
814. 二叉树剪枝
剖析
- 减掉的是不蕴含 1 的子树，所以能够自底向上，递归的将不符合条件的子树干掉
- 自底向上个别就是所谓的递归，始终搜寻（递）到叶子节点下的 null，而后开始往上（归）返回所得的的值，个别最初的返回值都是间接返回而不是外层的全局变量
- 对于每一个根节点，咱们都用递归函数求出剪枝后的左右子树，并且拼在以后的节点上，如果左右子树曾经剪掉了（null），同时本人的值也是 0，那么这个子树就能够剪掉，具体表现就是返回 null, 那么它的上一层父节点就能够辨认出这课子树没了，始终归到根节点，而后返回最终后果
- 工夫复杂度: O(N)
var pruneTree = function (root) {const recursion = (root) => {if (!root) return null; // 到叶子节点的下的 null 了
// 求出左右树
root.left = recursion(root.left);
root.right = recursion(root.right);
if (!root.left && !root.right && root.val === 0) return null; // 左右树都为 null，且本身值为 0，则这课子树减除
return root; // 还能够抢救一下
};
return recursion(root);
};
1325. 删除给定值的叶子节点
剖析
- 这里删除有两个规范：叶子节点 + target
- 一旦删除某个叶子节点，它的父节点很可能就
复阳，而后须要持续删除 - 所以自底向上的删除，应用后序遍历最合适了.
- 这题和楼上 814. 二叉树剪枝 根本一样，本题是给定值 target，上题是给定值 0，实质上都是剪枝
- 工夫复杂度: O(N)
var removeLeafNodes = function (root, target) {const postOrder = (root) => {if (!root) return null;
root.left = postOrder(root.left);
root.right = postOrder(root.right);
// 叶子节点且值等于 target 的时候
if (!root.left && !root.right && root.val === target) return null;
return root;
};
return postOrder(root);
};
1026. 节点与其先人之间的最大差值
剖析
- 采纳自顶向下的搜寻形式，在搜寻过程中，就携带以后路线的最大最小值，而后就能够配对出最大的差值了
- 须要留神的是，差值最低是两个节点，这个题目曾经限定好了，所以在函数中不须要再做判断，然而初始化的时候要留神
- 这里间接将根节点的值作为门路的初始 min, max 值，而后从根节点的子节点开始搜寻，所以有左右节点进行，最初返回最终的后果
- 工夫复杂度: O(N)
var maxAncestorDiff = function (root) {
let ret = 0;
const dfs = (root, min, max) => {if (!root) return;
ret = Math.max(ret, Math.abs(max - root.val), Math.abs(root.val - min));
min = Math.min(min, root.val);
max = Math.max(max, root.val);
dfs(root.left, min, max);
dfs(root.right, min, max);
};
// 题目给定起码两个节点，少于两个节点也的确无奈进行差值比拟
// 所以这里间接初始化的时候，根节点的值作为初始化的门路最大最小值
dfs(root.left, root.val, root.val);
dfs(root.right, root.val, root.val);
return ret;
};
865. 具备所有最深节点的最小子树
剖析 1 — 求出 depth 而后匹配
- 既然是要最大深度，那么就先自顶向下求出最大深度 max, 而后再自底向上返回根节点的最大深度，找出匹配最大深度对应最小节点树；— 这里匹配的时候须要先求出最大深度 depth，而后再一一匹配；
- 因为咱们要求的是最小的子树，然而这个子树要蕴含所有的最大深度节点，所以咱们递归返回的是以后节点子树的最大深度，只有当子树的左右子树同时存在最大深度的节点时，咱们才会替换到高度更高的树，即更大的树
- 先搜寻到叶子节点，在递归回根节点，工夫复杂度为 O(N)
var subtreeWithAllDeepest = function (root) {
let max = 0; // 最大深度
let ret = undefined; // 指标节点
const dfs = (root, depth) => {
// 叶子节点 -- 前序遍历求出最大深度
if (!root) {max = Math.max(max, depth); // 求出最大深度
return depth;
}
const left = dfs(root.left, depth + 1);
const right = dfs(root.right, depth + 1);
// 后序遍历依据左右子树的最大深度是否同时满足 max，判断是否须要替换成更大的子树
if (left === max && right === max) {
// 只有在两子树的最大深度同时等于最大深度的时候，才需置换节点
ret = root;
}
// 后序遍历完了，达到根节点
return Math.max(left, right); // 返回的是以后节点子树中的的最大深度
};
dfs(root, 0);
return ret;
};
剖析 2 — 深度不比求进去
- 之前是用全局变量保留最大深度和最小的树，实际上在每一次递归中，咱们都能失去左右子树的状况，包含子树中
最大的深度以及对应的最小子树, - 所以递归 return 回来
最大的深度以及对应的最小子树，就能够不须要额定的变量了 - 实际上咱们基本不须要晓得具体的最大深度是多少，只须要比拟深度，失去最大的那个即可
var subtreeWithAllDeepest = function (root) {const dfs = (root, depth) => {if (!root) return [root, depth];
const [lr, ld] = dfs(root.left, depth + 1); // lr -- left root, ld -- left depth
const [rr, rd] = dfs(root.right, depth + 1);
if (ld === rd) return [root, ld]; // 如果左右树的最大值雷同，即最大深度节点两边都有，所以要更新一下最小树节点
if (ld > rd) return [lr, ld];
if (ld < rd) return [rr, rd];
};
return dfs(root, 0);
};
1530. 好叶子节点对的数量
剖析
- 看题求所有的好叶子节点对，既然是叶子节点之间做文章，自底向上的去求两者间隔，感觉比拟合乎直觉
- 后序遍历到叶子节点, 开始返回，因为一个节点的叶子节点树可能不止一个，所以要用数组保留
- 递归回来的叶子节点数组，都得更新节点到叶子节点的间隔数组
- 而后找出左右节点间隔中符合要求的节点，最初将所有叶子节点合并起来返回
- 工夫复杂度 O(N), 空间复杂度 O(N)
var countPairs = function (root, distance) {
const ret = 0;
const dfs = (root) => {if (!root) return [];
if (!root.left && !root.right) return [0]; // 叶子节点
// 求出叶子节点到以后节点的间隔
const left = dfs(root.left).map((i) => i + 1);
const right = dfs(root.right).map((i) => i + 1);
// 而后找出所有小于 dis 的节点对
for (let l of left) {for (let r of right) {if (l + r <= distance) ret++;
}
}
// 将叶子节点合起来返回回去
return [...left, ...right];
};
dfs(root);
return ret;
};
894. 所有可能的满二叉树
剖析
- 如果给定的 n 是偶数，那么间接返回空的数组，因为不能组成满二叉树，而如果只有 1 个节点，则能够返回 [node] — 这个是边界
- 对于每一个子树而言，都是在构建
满二叉树, 只是对应的节点数 n 有所区别而言 — 换句话说，对于每一个子节点，都要进行一次构建满二叉树，晓得边界为止 - 每一层都是遍历调配左右树的节点数，而后应用
后续遍历的形式遍历到边界条件处，而后开始进行解决； - 只有当左右节点树都存在节点的时候，才须要进行拼接，组合成新的节点数组往上递归
- 整体就是自顶向下调配子树节点数，来求满二叉树；而后自低向上组合更新节点树，最初失去一个合规的满二叉树节点数组；
- 工夫复杂度 N2, 每一层都须要遍历切割，切割完之后别离进行树的创立
var allPossibleFBT = function (n) {const recursion = (n) => {if (n % 2 === 0) return []; // 偶数
if (n === 1) return [new TreeNode(0)];
const ret = []; // 保留以后节点下，所有满足 ` 满二叉树 ` 状况的节点
for (let i = 0; i < n; i++) {
const left_num = i,
right_num = n - i - 1; // 之所以再减去 1 个，因为根节点占据了 1
// 构建左树的满二叉树
const lefts = recursion(left_num);
const rights = recursion(right_num);
if (lefts && rights) {
// 必须同时存在的时候，才是满的；要不都没有
for (let l of lefts) {for (let r of rights) {const root = new TreeNode(0);
root.left = l;
root.right = r;
ret.push(root);
}
}
}
}
return ret;
};
return recursion(n);
};
96. 不同的二叉搜寻树
剖析 — 暴力拆分法
- 对于 BST 中每一个子节点，他们所在的子树也是 BST，所以咱们要求 [1,n] 有多少个不同的 BST，能够拆解成 N 种形式的子树汇合，比方说给定的 n == 3，则能够拆解成 [0,2],[1,1],[2,0] 三种左右子树节点调配
- 所以咱们能够一直网下拆分，边界条件是节点数为 1 或者 0 的时候，就只有一种状况了，而后开始返回
- 最初递归回来的值就是咱们想要的值。
- 工夫复杂度 n2logn
var numTrees = function (n) {const recursion = (n) => {if (n === 0) return 1;
if (n === 1) return 1;
let temp = 0;
for (let i = 1; i <= n; i++) {
const l = i - 1,
r = n - i;
const left = recursion(l);
const right = recursion(r);
temp += left * right;
}
return temp;
};
return recursion(n);
};
剖析 — dp
- 基于下面的实践，发现其实对于可能造成多少个 BST 只和有序数组数量 n 无关，而且咱们最终只是求一个总值而不是各种状况的树的汇合；
- 所以在拆解过程中，会一直反复的去进行递归操作，返回对应的值，这些值其实是能够保存起来间接应用的，比方说 fn(1) = 1.fn(2) = 2 等，能够用一个汇合保存起来，而后求的时候间接返回而不必再进行递归。
- 而后就想到了应用 dp 的形式，dp[i] 示意的就是有 i 有值的有序数组能够有多少不同的 BST
- 边界条件：dp[0] = dp[1] = 1
- 状态转移方程: dp[i] = Sum(dp[k]*dp[i-k]) 左右两树别离给与不同的节点数，他们之间的乘积就是其中一种状况的总和，再累加起来即可，这个时候因为后面小的 dp 值曾经存在，所以能够 O(1)的模式求出 dp[k] 和 dp[i-k]
- 工夫复杂度 O(NlogN), 空间复杂度 N
var numTrees = function (n) {const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {for (let j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
};
437. 门路总和 III
剖析
- 关键点，门路必须向下，也就是不可以往上反复；
- 而后终点不用是根节点，所以须要有一个 dfs 遍历不同的终点
- 起点不肯定是叶子节点，所以可能在半途就失去合规的门路，然而因为值有正有负，所以必须走到叶子节点，能力保障不脱漏
- outer 负责前序遍历获取其实节点，inner 负责以某个子树节点为终点，找出和为 targetSum 的门路
- 工夫复杂度 O(NlogN)
var pathSum = function (root, targetSum) {
let ret = 0;
const inner = (root, sum) => {
const temp = sum + root.val;
if (temp === targetSum) ret++;
if (root.left) inner(root.left, temp);
if (root.right) inner(root.right, temp);
};
const outer = (root) => {if (!root) return;
inner(root, 0);
outer(root.left);
outer(root.right);
};
outer(root);
return ret;
};
艰难题
987. 二叉树的垂序遍历
剖析
- 这道题次要还是看图做题，下面都标记了一些垂序的坐标，所以就思考遍历一次，给节点标注上垂序地位属性，而后将雷同垂序地位的放在同一个数组中即可；
- 值得注意的是，在二叉树互相交替的子树中，同一层中会呈现多个垂序地位一样的值，这个时候题目也通知怎么解决了
同行同列雷同时，才会将值从小到大排序； - 所以不能间接将所有垂序地位雷同的值，存储到全局的 map 中，而是须要在每一层有一个变量 tempMap，解决好可能存在的同层同列的值的程序后，再合并到全局的 map；
- 遍历完树失去一个 map 后，key 是垂序地位，value 是相应的值，是一个数组
- 对 key 值进行排序后转成一个合规的数组即可
- 空间复杂度 O(N), 工夫复杂度 O(N) + O(MlogM), 其中 N 是树的节点值，M 是垂序地位宽度
var verticalTraversal = function (root) {const ret = []
const queue = []
const map = new Map(); // 总的存储不同垂序地位的数组
queue.push([root,0]) // 第一个参数的节点，第二个参数是垂序间隔 -- 这里以根节点为 0
while(queue.length) {
let len = queue .length
const tempMap = new Map() // 每一层的长期 map
while(len--){
// 进入每一层解决
const [root,index] = queue.shift()
if(root.left) queue.push([root.left,index-1])
if(root.right) queue.push([root.right,index+1])
// 解决以后节点的寄存地位
if(tempMap.has(index)){tempMap.set(index,tempMap.get(index).concat(root.val))
}else{tempMap.set(index,[root.val])
}
}
for(let [index,val] of tempMap.entries()){val.sort((a,b) =>a-b)
if(map.has(index)){map.set(index,map.get(index).concat(val))
}else{map.set(index,val)
}
}
}
// 解决完了
return [...map.keys()].sort((a,b) => a-b).map(key => map.get(key))
}
2. 剑指 Offer 37. 序列化二叉树
- 这道题其实就是让你理解一下，为啥咱们做树题的时候，明明在做树题（或者链表）这些题目的时候，控制台的例子都是数组，而不是一个可视化的树结构的数据，之前我始终很难了解，直到理解到序列化和反序列化之后。
- 集体了解这是为了兼容不同语言内置数据结构的不同而做进去的优化策略，比方说 JS 就没有树这种构造，所以咱们在做树的时候，须要本人构建一个类，而后用咱们罕用的数据结构转成树，而后再进行运算，而这个过程，其实就是树的反序列化。而数组，字符串这些作为根本数据结构，简直在罕用语言中都会内置，所以就成了树这些构造序列化构造的优先选择。
剖析 — 序列化 — 节点转成字符串
- 咱们主观上看一个反序列化的数组或者字符串的时候，也是从上到下，从左到右进行匹配，所以咱们再做序列化的时候，就间接应用的 bfs 了
- 须要留神的是，这里是间接用单个字符串存储，最初会有一个 “,” 多进去，须要去除
- 工夫复杂度和空间复杂度都是：O(N),
var serialize = function (root) {if (!root) return "";
let ret = "";
const queue = [];
queue.push(root);
while (queue.length) {
let len = queue.length;
let isNull = true; // 确定一下这一层是不是全是 null，如果是, 那么就要完结了
let str = "";
while (len--) {const root = queue.shift();
if (!root) {
// 因为在反序列化的时候，你可不晓得以后一层对应的节点的地位在哪里，所以只能用 null 来做占位符了
str += "null"+ ",";
} else {
isNull = false;
str += root.val + ",";
queue.push(root.left);
queue.push(root.right);
}
}
// 一层遍历完了
if (isNull) {
// 这一层都是 null，所以完结了
return ret.substr(0,ret.length-1);
} else {ret += str; // 将字符串加上}
}
};
剖析 — 反序列化 — 字符串转成节点
- 给定一个数组，反序列化出一课树
- 应用的是 BFS 平铺的形式，每次取走 nodes 中的两个节点，如果有值，则保留到队列中，保障循环完结前将所有有值的节点和对应的左右节点都串联好。
- 具体来说就是 queue 保留有值的节点, index 获得弹出节点的左右子节点（左右节点是保留在 nodes 中的）
- 工夫复杂度和空间复杂度都是：O(N)；
var deserialize = function (data) {if(!data) return null // 空节点
const nodes = data.split(',') // 切割成数组
const root = new TreeNode(nodes[0]); // 根节点
const queue = [] // 队列，用来存储每一层的节点；queue.push(root)
let index = 0; // 以后节点的下标
while(index < nodes.length - 2){const root = queue.shift()
const lv = nodes[index+1]
const rv = nodes[index+2]
if(lv!== 'null') {const lnode = new TreeNode(lv)
root.left = lnode
queue.push(lnode)
}
if(rv!== 'null') {const rnode = new TreeNode(rv)
root.right = rnode
queue.push(rnode)
}
index +=2
}
return root
};
124. 二叉树中的最大门路和
剖析
- 求以某个节点最根节点的最大门路和，和以这个节点为截止点的最大门路和，是两个不一样的值
- 前者根节点是门路中的一环，如果 l -> root -> r
- 而后者是作为子树的最大单边门路和，返回给父节点，让父节点进行判断，如 l(e) -> root
- 所以整体来说就是一个递归过程，然而在递归的过程中又存在部分最优解须要保留；
- 每一次的递归的最大值是蕴含
根节点的最大值，这样能够保障连接上左右子树的最大值，如果其中一课子树的最大值比这个大，那么在前面递归中天然会代替以后值，不须要额定解决 - 工夫复杂度是 O(N), 空间复杂度是 O(1)
var maxPathSum = function(root) {
let max = -Infinity
const dfs = root => {if(!root) return 0
const l = dfs(root.left)
const r = dfs(root.right)
// 这里的 root.val 不须要和 0 比拟，必须蕴含根节点，否则无奈连接
// 同时单子树最大值如果更大，会在前面的 dfs 中取代 max
const tempMax = Math.max(l,0)+Math.max(r,0)+root.val
max =Math.max(max,tempMax)
return Math.max(0,l,r)+root.val // 这里的根节点是必须存在的，不然没法连接上
}
dfs(root)
return max
};
834. 树中距离之和
参考题解: leetcode-cn.com/problems/su…
剖析
- nodeNum 存储的是子树 root 总的节点数，包含所有子节点和以后根节点 — nodeNum[root] = sum(nodeNum[child])+1
- distSum 存储的是所有子节点到的根节点 root 的总间隔，包含了所有子树的 distSum 和这些子树节点再往上走一步的间隔之和 — distSum[root] = sum(dist[child]+nodeNum[root])
- distSum 有点不好了解，其实就是从下往上递归求出子树的总间隔，那么父节点的总间隔就等于这些子树间隔之和，而后还要让这些子树节点全副加 1 的间隔，也就是 Sum(nodeNum[child])*1
- 这里的 distSum 求得的是，子树间隔之和，还须要从上往下递归求出真正的全副节点的间隔之和
- 须要留神的是，这里只是一个模仿的树，保留的数组其实是节点左近的所有节点，之所以分父子节点，是为了保障咱们再遍历过程中先走的节点为父节点，后走的节点为子节点而已；所以这个连线其实没有理论的指向关系
var sumOfDistancesInTree = function(n, edges) {const graph= new Array().fill(null).map(() => []) // 下标就是根节点的坐标，值就是子节点的坐标数组
for(let [from,to] of edges){graph[from].push(to)
graph[to].push(from)
}
const distSum = new Array(n).fill(0) // 1. 存储的是子树节点的间隔之和
const nodeNum = new Array(n).fill(1) // 存储的是子树总的节点数，起码都有一个
// 这里是自底向上求出每个节点的 distSum 和 nodeNum，所以用后续遍历
const postOrder = (root,parent) => {const childs = graph[root]
for(let child of childs) {if(child === parent) continue // parent 节点就是之前刚走过的节点
postOrder(child,root)
nodeNum[root] += nodeNum[child]
distSum[root] += distSum[child]+nodeNum[child]
}
}
// 用前序遍历更新 distSum, 这个时候 distSum 就变成了全副节点的间隔和
const preOrder = (root,parent) => {const childs = graph[root]
for(let child of childs) {if(child === parent) continue // parent 节点就是之前刚走过的节点
distSum[child] = distSum[root] - nodeNum[child] + (n- nodeNum[child])
preOrder(child,root)
}
}
postOrder(0,-1)
preOrder(0,-1)
return distSum
};