1.minmax 面试题

image.png
代码：（就是代码能力），也是比较邪乎的递归解法

  1. function test(mat) {
  2.     let rows = mat.length;
  3.     let columns = mat[0].length;
  5.     let result = [];
  7.     let [row, column] = [0, 0];
  9.     function goUpRight() {
  10.         result.push(mat[row][column]);
  12.         while(inMat([row - 1, column + 1])) { // 能走才走
  13.             [row, column] = [row - 1, column + 1];
  14.             result.push(mat[row][column]);
  15.         }
  17.         if (inMat([row, column + 1])) { // go right
  18.             [row, column] = [row, column + 1];
  19.             goDownLeft();
  20.         } else if (inMat([row + 1, column])) { // go down
  21.             [row, column] = [row + 1, column];
  22.             goDownLeft();
  23.         }
  24.     }
  25.     function goDownLeft() {
  26.         result.push(mat[row][column]);
  28.         while(inMat([row + 1, column - 1])) {
  29.             [row, column] = [row + 1, column - 1];
  30.             result.push(mat[row][column]);
  31.         }
  33.         if (inMat([row + 1, column])) { // go down
  34.             [row, column] = [row + 1, column];
  35.             goUpRight();
  36.         } else if (inMat([row, column + 1])) { // go right
  37.             [row, column] = [row, column + 1];
  38.             goUpRight();
  39.         }
  40.     }
  42.     function inMat([row, column]) {
  43.         if (0 <= row && row < rows && 0 <= column && column < columns) {
  44.             return true;
  45.         }
  47.         return false;
  48.     }
  50.     goUpRight();
  52.     return result;
  53. }
  55. test([[1, 2, 3], [4, 5, 6], [7,8,9]]);

2.863. 二叉树中所有距离为 K 的结点

原始状态：我写的，原理简单，但是很难在面试场上做出来

  1. ar distanceK = function(root, target, k) { // 这道题使用了 层遍历 和 dfs，好复杂，把这段时间的训练都使用了
  2.     if (k < 0) {
  3.         return [];
  4.     }
  5.     if (k === 0) {
  6.         return [target.val];
  7.     }
  9.     let targetPath = [];
  10.     let targetNode = null;
  12.     function dfs(node, path) {
  13.         if (!node) {
  14.             return;
  15.         }
  16.         if (node.val === target.val) {
  17.             targetPath = path;
  18.             targetNode = node;
  19.             return;
  20.         }
  22.         dfs(node.left, [node, ...path]);
  23.         dfs(node.right, [node, ...path]);
  24.     }
  26.     dfs(root, []); // 先找到这个 node
  28.     if (!targetNode) { // 没找到
  29.         return targetPath;
  30.     }
  32.     function levelWalk(node, from, k) { // 层遍历
  33.         if (k <= 0) {
  34.             return [];
  35.         }
  36.         let maxLevel = k;
  37.         let queue = [node];
  38.         while (queue.length > 0) {
  39.             let size = queue.length;
  41.             if (maxLevel === 0) {
  42.                 queue = queue.filter(node => node).map(node => node.val);
  43.                 return queue;
  44.             }
  46.             for (let i = 0; i < size; i++) {
  47.                 node = queue.shift();
  48.                 if (!node) {
  49.                     continue;
  50.                 }
  51.                 if (node.left !== from) { // 不走回头路
  52.                     queue.push(node.left);
  53.                 }
  54.                 if (node.right !== from ) { // 不走回头路
  55.                     queue.push(node.right);
  56.                 }
  57.             }
  58.             maxLevel--;
  59.         }
  60.         return [];
  61.     }
  63.     let ans = levelWalk(targetNode, targetPath[0], k);
  65.     let from = targetNode;
  66.     while (targetPath.length > 0) {
  67.         let parent = targetPath.shift();
  68.         if (k === 1) {
  69.             ans.push(parent.val);
  70.             break;
  71.         } else { // k > 1
  72.             let _ans = levelWalk(parent, from, --k); // 递归层遍历
  73.             ans.push(..._ans);
  74.             from = parent;
  75.         }
  76.     }
  78.     return ans;
  79. };

进化形态：
https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree/solution/er-cha-shu-zhong-suo-you-ju-chi-wei-k-de-qbla/

  1. var distanceK = function(root, target, k) {
  2.     const parents = new Map();
  3.     const ans = [];
  5.     const findParents = (node) => {
  6.         if (node.left != null) {
  7.             parents.set(node.left.val, node);
  8.             findParents(node.left);
  9.         }
  10.         if (node.right != null) {
  11.             parents.set(node.right.val, node);
  12.             findParents(node.right);
  13.         }
  14.     }
  16.     // 从 root 出发 DFS，记录每个结点的父结点
  17.     findParents(root);
  19.     const findAns = (node, from, depth, k) => {
  20.         if (node == null) {
  21.             return;
  22.         }
  23.         if (depth === k) {
  24.             ans.push(node.val);
  25.             return;
  26.         }
  27.         if (node.left !== from) {
  28.             findAns(node.left, node, depth + 1, k);
  29.         }
  30.         if (node.right !== from) {
  31.             findAns(node.right, node, depth + 1, k);
  32.         }
  33.         if (parents.get(node.val) !== from) {
  34.             findAns(parents.get(node.val), node, depth + 1, k);
  35.         }
  36.     }
  37.     // 从 target 出发 DFS，寻找所有深度为 k 的结点
  38.     findAns(target, null, 0, k);
  40.     return ans;
  41. };

最高级形态：
https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree/solution/yi-shu-jian-tu-qi-fa-si-lu-by-fan-hang-9-4spo/

  1. var distanceK = function(root, target, k) {
  2.     const parents = new Map();
  3.     const ans = [];
  5.     parents.set(root, null);
  7.     function dfs(node) {
  8.         if (!node) {
  9.             return;
  10.         }
  11.         if (node.left) {
  12.             parents.set(node.left, node);
  13.             dfs(node.left);
  14.         }
  15.         if (node.right) {
  16.             parents.set(node.right, node);
  17.             dfs(node.right);
  18.         }
  19.     }
  21.     dfs(root);
  23.     const visitedNodes = new Set(); // 就像大火烧过的路径
  25.     function search(node, depth) { // dfs 过程增加 深度参数，这也是第一次使用
  26.         if (!node) {
  27.             return;
  28.         }
  30.         if (visitedNodes.has(node)) {
  31.             return;
  32.         }
  34.         if (depth === k) {
  35.             ans.push(node.val);
  36.             return;
  37.         }
  39.         visitedNodes.add(node);
  41.         search(node.left, depth + 1);
  42.         search(node.right, depth + 1);
  43.         let parent = parents.get(node);
  44.         search(parent, depth + 1);
  45.     }
  47.     search(target, 0);
  49.     return ans;
  50. };

3.1110. 删点成林

https://leetcode-cn.com/problems/delete-nodes-and-return-forest/solution/hou-xu-bian-li-yi-chong-jian-dan-de-si-l-5muy/

  1. var delNodes = function(root, to_delete) {
  2.     // 利用 后序遍历的性质，无需专门做 parents 的map
  3.     // let parents = new Map();
  5.     // parents.set(root, null);
  7.     // function dfs(node) {
  8.     //     if (!node) {
  9.     //         return;
  10.     //     }
  11.     //     if (node.left) {
  12.     //         parents.set(node.left, node);
  13.     //         dfs(node.left);
  14.     //     }
  15.     //     if (node.right) {
  16.     //         parents.set(node.right, node);
  17.     //         dfs(node.right);
  18.     //     }
  19.     // }
  21.     // dfs(root);
  23.     let ans = [root];
  24.     let to_delete_set = new Set(to_delete);
  26.     function doDelete(node) { // 返回头节点
  27.         if (!node) {
  28.             return null; // 这里要返回 null 才行，leetcode 内部使用是 ts 来检验，很恶心
  29.         }
  31.         // 写到前面
  32.         node.left = doDelete(node.left);
  33.         node.right = doDelete(node.right);
  35.         if (to_delete_set.has(node.val)) {
  36.             to_delete_set.delete(node.val);
  38.             if (ans.includes(node)) {
  39.                 let index = ans.indexOf(node);
  40.                 ans.splice(index, 1);
  41.             }
  43.             if (node.left) {
  44.                 ans.push(node.left);
  45.             }
  46.             if (node.right) {
  47.                 ans.push(node.right);
  48.             }
  51.             return null;
  52.         }
  54.         return node;
  55.     }
  57.     doDelete(root);
  59.     return ans;
  60. };

103. 二叉树的锯齿形层序遍历

一般的层序遍历，其实很简单。 和 102. 二叉树的层序遍历 解法一致。

  1. var zigzagLevelOrder = function(root) {
  2.     let ans = [];
  3.     if (!root) {
  4.         return ans;
  5.     }
  7.     let queue = [root];
  8.     let leftToRight = true;
  9.     while (queue.length) {
  10.         let size = queue.length;
  11.         let level = [];
  12.         for (let i = 0; i < size; i++) {
  13.             let cur = queue.shift();
  14.             level.push(cur);
  15.             cur.left && queue.push(cur.left); // 只存在有值时，才填入
  16.             cur.right && queue.push(cur.right);
  17.         }
  18.         let tmp = [];
  19.         for (let node of level) {
  20.             if (leftToRight) {
  21.                 tmp.push(node.val);
  22.             } else {
  23.                 tmp.unshift(node.val);
  24.             }
  25.         }
  26.         ans.push(tmp);
  27.         leftToRight = !leftToRight; // 翻转方向
  28.     }
  30.     return ans;
  31. };