二叉树的最近公共祖先 && 除自身以外数组的乘积

• 二叉树的最近公共祖先 && 除自身以外数组的乘积
  • 二叉树的最近公共祖先
    • 题目详情
    • 解题思路
    • 代码实现
• 除自身以外数组的乘积
  • 题目详情
  • 解题思路
  • 代码实现

二叉树的最近公共祖先

题目详情

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

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

解题思路

使用后序遍历实现，递归调用左右子树，如果左右子树皆为 true，则该节点就是最近的公共祖先节点

代码实现

var lowestCommonAncestor = function(root, p, q) {

  let res = null;
  function dfs(node) {
    if (!node) return false
    const left = dfs(node.left)
    if (res) return true
    const right = dfs(node.right)
    if (res) return true // 如果已经找到结果，直接返回true

    // 如果左右子树都找到了目标节点，或者当前节点就是目标节点并且它的一个子树找到了另一个目标节点
    if (left && right || (node.val === p.val || node.val === q.val) && (left || right)) {
      res = node // 当前节点就是最近公共祖先
    }
    // 如果左子树或右子树找到了目标节点，或者当前节点就是目标节点，返回true
    return left || right || node.val === p.val || node.val === q.val
  }
  dfs(root) // 从根节点开始遍历
  return res // 返回结果
};

除自身以外数组的乘积

题目详情

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

解题思路

完全没审题，直接使用了除法（乐了 后面发现可以用前缀和的方法来做，具体：

创建两个数组，L 和 R。对于给定索引 i，L[i] 表示 nums[i] 左侧所有数字的乘积，R[i] 表示 nums[i] 右侧所有数字的乘积。

代码实现

• 除法

  let res = []
  let all = nums.reduce((acc, cur) => cur === 0 ? acc : acc * cur, 1)
  let zeroCount = nums.filter(n => n === 0).length
  for (num of nums) {
    if (zeroCount > 1) res.push(0)
    if (zeroCount === 1) res.push(num === 0 ? all : 0)
    if (zeroCount === 0) res.push(all / num)
  }
  return res

• 前缀和

  // 创建一个数组 L，L[i] 表示 nums[i] 左侧所有元素的乘积
  let L = new Array(nums.length).fill(1)
  // 创建一个数组 R，R[i] 表示 nums[i] 右侧所有元素的乘积
  let R = new Array(nums.length).fill(1)
  let res = []
  for (let i = 1; i < nums.length; i++) {
    L[i] = L[i - 1] * nums[i - 1]
  }
  for (let i = nums.length - 2; i >= 0; i--) {
    R[i] = R[i + 1] * nums[i + 1]
  }
  for (let i = 0; i < nums.length; i++) {
    res.push(L[i] * R[i])
  }
  return res