LeetCode之二叉树

上篇中介绍了二叉树的基本概念和操作。本篇着重于实际问题。

545.Boundary of Binary Tree
定义树的左边界为根节点到最左节点的路径，右边界为根节点到最右节点的路径。最左节点为从根节点能到达的最左叶子节点，若没有左子树存在右子树，能在右子树中找最左节点，对于根而言若不存在左子树则根为最左节点；同理最右节点。
要求逆时针输出：左边界+叶子节点+右边界（输出不能存在重复节点）
Input:

     ____1_____
    /          \
   2            3
  / \          /
 4   5        6
    / \      / \
   7   8    9  10

Output:[1,2,4,7,8,9,10,6,3]

分析：分别找出左边界、右边界及叶子节点；

var boundaryBT = function (root) {
  if (root === null) return [];
  return getBoundryPath(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]。

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];
};