day19 题目： 剑指 Offer 64. 求 1+2+……+n、剑指 Offer 68 - I. 二叉搜索树的最近公共祖先、剑指 Offer 68 - II. 二叉树的最近公共祖先

知识点：树、递归、dfs/bfs，难度为中等、简单、简单

学习计划链接：「剑指 Offer」 - 学习计划

剑指 Offer 64. 求 1+2+……+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

• 1 <= n <= 10000

思路与代码

看这题的 tag：脑筋急转弯就能发现不对劲……

主要就是用短路运算符来代替条件判断

/**
 * @param {number} n
 * @return {number}
 */
var sumNums = function (n) {
  n && (n += sumNums(n - 1));
  return n;
};

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

思路与代码

根据之前冲刺春招-精选笔面试 66 题大通关 17的经验，思路一为先从一个节点往上走将沿途的 vis 置为 true，再从另一个结点往上走，遇到 vis 为 true 的就是最近共同祖先，返回。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root) return null;
  let fa = new Map();
  function dfs(rt, pre) {
    if (rt === null) return;
    fa.set(rt, pre);
    dfs(rt.left, rt);
    dfs(rt.right, rt);
  }
  dfs(root, null);
  let vis = new Map();
  let nowv = q;
  while (nowv) {
    vis.set(nowv, true);
    if (fa.has(nowv)) nowv = fa.get(nowv);
  }
  nowv = p;
  while (nowv) {
    if (vis.has(nowv)) return nowv;
    if (fa.has(nowv)) nowv = fa.get(nowv);
  }
};

思路二则是利用二叉搜索树的性质，从根节点开始遍历，官方题解如下：

• 若当前节点值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，将当前节点移动到它的左子节点；
• 若当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，将当前节点移动到它的右子节点；
• 若等于当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root) return null;
  if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
  else if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
  else return root;
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

注意：本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

思路与代码

用上题的思路 1 就好了。

fa存每个结点的父节点，从上向下遍历一次初始化fa，再从下往上初始化 vis

var lowestCommonAncestor = function (root, p, q) {
  if (!root) return null;
  let fa = new Map();
  function dfs(rt, pre) {
    if (rt === null) return;
    fa.set(rt, pre);
    dfs(rt.left, rt);
    dfs(rt.right, rt);
  }
  dfs(root, null);
  let vis = new Map();
  let nowv = q;
  while (nowv) {
    vis.set(nowv, true);
    if (fa.has(nowv)) nowv = fa.get(nowv);
  }
  nowv = p;
  while (nowv) {
    if (vis.has(nowv)) return nowv;
    if (fa.has(nowv)) nowv = fa.get(nowv);
  }
};