千位分隔数、二叉树的最近公共祖先、二叉树的锯齿形层次遍历

千位分隔数

题目描述

给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。

示例 1：

输入：n = 987

输出："987"

示例 2：

输入：n = 0

输出："0"

题解

注意 reverse 是数组方法，而非字符串方法

tsCopy
function thousandSeparator(n: number): string {
  return [...n.toString()]
    .reverse()
    .map((digit, i) => (i > 0 && i % 3 === 0 ? "." + digit : digit))
    .reverse()
    .join("");
}

二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路

有三种情况：

1. 当前子节点为空、为 p 或者 q：直接返回它本身

2. 左右都有值：说明找到了公共祖先，直接返回祖先

3. 只有一边有值：说明 p 和 q 都在同一边，可能已经找到了公共祖先，所以返回有值的一边

题解

tsCopy
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left !== null && right !== null) {
    return root;
  }

  return left !== null ? left : right;
}

二叉树的锯齿形层序遍历

题目描述

给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

题解

tsCopy
function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const res: number[][] = [];
  const queue: TreeNode[] = [root];
  let isLeftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (isLeftToRight) {
        level.push(node.val);
      } else {
        level.unshift(node.val); // 从前面插入，实现反向
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    res.push(level);
    isLeftToRight = !isLeftToRight;
  }

  return res;
}