545.Boundary of Binary Tree 定义树的左边界为根节点到最左节点的路径,右边界为根节点到最右节点的路径。最左节点为从根节点能到达的最左叶子节点,若没有左子树存在右子树,能在右子树中找最左节点,对于根而言若不存在左子树则根为最左节点;同理最右节点。 要求逆时针输出:左边界+叶子节点+右边界(输出不能存在重复节点) Input:
var boundaryBT = function (root) { if (root === null) return []; returngetBoundryPath(root, 1).concat(getLeaves(root).concat(getBoundryPath(root.right, 2))); }; //flag==1:left boundary, flag==2:right boundary var getBoundryPath = function (node, flag) { var res = []; while (node.left !== null || node.right !== null) { res.push(node.val); node = flag == 1 ? (node.left !== null ? node.left : node.right) : (node.right !== null ? node.right : node.left); } return flag == 1 ? res : res.reverse(); };
var getLeaves = function (root) { var nodes = [], res = []; if (root === null) return res; nodes.push(root); var p; while (nodes.length !== 0) { p = nodes.shift(); if (p.left !== null) nodes.push(p.left); if (p.right !== null) nodes.push(p.right); if (p.left == null && p.right == null) res.push(p.val); } return res; };
549.Binary Tree Longest Consecutive Sequence II 在二叉树中找出最长的连续(+1或-1)路径长度,可连续增序或连续降序。路径可以是child-parent-child遍历。
思路:自顶向下的动态规划 len = max(len, max(Inclen(left),Inclen(right))+ max(Declen(left),Declen(right)) -1)。 max(Inclen(left),Inclen(right))与max(Declen(left),Declen(right))分别表示从左子树(右子树)叶结点到当前结点的最长连续增长与连续减小长度。
var longestConsecutive = function (root) { var cnt = [0]; pathHelper(root, cnt); return cnt[0]; }; var pathHelper = function (root, cnt) { if (root == null) return [0, 0]; //num[0] increase;num[1] decrease var num = [1, 1]; if (root.left !== null) { var l = pathHelper(root.left, cnt); if (root.val == root.left.val - 1) num[0] = l[0] + 1; if (root.val == root.left.val + 1) num[1] = l[1] + 1; } if (root.right !== null) { var r = pathHelper(root.right, cnt); if (root.val == root.right.val - 1) num[0] = Math.max(num[0], r[0] + 1); if (root.val == root.right.val + 1) num[1] = Math.max(num[1], r[1] + 1); } cnt[0] = Math.max(cnt[0], num[0] + num[1] - 1); return num; };
582.Kill Process 两个数组分别表示进程的PID与进程父PID(PPID),根节点PPID为0,输入要杀的进程,输出最终杀的进程PID。(父进程杀掉后其子进程也会被杀掉)
思路:利用数组建立哈希表{PPID:[PID1,…,PIDn]。
1 2 3 4 5 6 7 8 9
var killProcess = function (PIDs, PPIDs, k) { var map = {}; for (var i = 0; i < PPIDs.length; i++) { if (!map[PPIDs[i]]) map[PPIDs[i]] = []; map[PPIDs[i]].push(PIDs[i]); } map[k].unshift(k); return map[k]; };