剑指 Offer 54. 二叉搜索树的第 k 大节点、剑指 Offer 57 - II. 和为 s 的连续正数序列、剑指 Offer 32 - II. 从上到下打印二叉树 II

剑指 Offer 54. 二叉搜索树的第 k 大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制：
1 ≤ k ≤ 二叉搜索树元素个数

思路

二叉搜索树的中序遍历结果就是有序数组，若先右后左则为递减数组，先左后右为递增数组。
可先右后左遍历后返回，数组第 k-1 个元素，则为结果。
或者使用计数，当 count===k-1 时设置 res 为节点值。注意判断 res 中是否有值，有的话不在进行遍历。

解答

返回数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
  const res = [];
  visit(root, res, k);
  return res[k - 1];
};

const visit = (node, res, k) => {
  if (!node) return;
  visit(node.right, res, k);
  res.push(node.val);
  visit(node.left, res, k);
};

改进

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function (root, k) {
  let res;
  let count = 0;
  const visit = (node) => {
    if (!node) return;
    if (!res) visit(node.right);
    if (count++ === k - 1) {
      res = node.val;
      return;
    }
    if (!res) visit(node.left);
  };
  visit(root);
  return res;
};

剑指 Offer 57 - II. 和为 s 的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

• 1 <= target <= 10^5

思路

暴力

双重循环，判断几个连续的值是否等于目标值即可。

滑窗

当长度大于 2 时，设置左窗口边界为 1，右窗口边界为 2。
例如 9=Math.ceil(9/2)+X = 5+X X 必然小于 5。
所以循环的出口为左窗口边界小于 Math.ceil(target/2)，且左窗口边界小于右窗口边界。
在每个循环中，求窗口内的和，若和小于 target，令右窗口边界加一。若大于 target，令左窗口边界加一。
若等于 target，存储窗口内的数组到结果数组中。

解答

暴力

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function (target) {
  const res = [];
  for (let i = 1; i < target; i++) {
    let sum = 0;
    let tmp = [];
    for (let j = i; j < target && sum < target; j++) {
      sum += j;
      tmp.push(j);
    }
    if (sum === target) res.push(tmp);
  }
  return res;
};

console.log(findContinuousSequence(2));

滑窗

/**
 * @param {number} target
 * @return {number[][]}
 */
var findContinuousSequence = function (target) {
  if (target.length < 2) return [];
  let start = 1;
  let end = 2;
  const res = [];
  while (end <= Math.ceil(target / 2) && start < end) {
    let sum = 0;
    for (let i = start; i <= end; i++) {
      sum += i;
    }
    if (sum === target) {
      let tmp = [];
      for (let i = start; i <= end; i++) {
        tmp.push(i);
      }
      res.push(tmp);
    }
    if (sum < target) {
      end++;
    } else {
      start++;
    }
  }
  return res;
};

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

1. 节点总数 <= 1000

思路

使用队列广度遍历思想。其中 splice 后再 for of，也是相当于队列出队后再将左右节点入队。

解答

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  const queue = [];
  const res = [];
  queue.push(root);
  let tmp = [];
  while (queue.length) {
    const nodes = queue.splice(0, queue.length);
    for (const node of nodes) {
      tmp.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(tmp);
    tmp = [];
  }
  return res;
};