「每日LeetCode」2020年9月25日

本文最后更新于：2023年3月19日 晚上

Lt116. 填充每个节点的下一个右侧节点指针、dfs、递归
剑指 Offer 47. 礼物的最大价值、动态规划

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

1
2
3
4
5
3
 / \
9  20
  /  \
 15   7

思路

转自力扣评论：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/comments/
首先要知道一个结论，前序/后序+中序序列可以唯一确定一棵二叉树，所以自然而然可以用来建树。
看一下中序和后序有什么特点，中序[9,3,15,20,7] ，后序[9,15,7,20,3]；
有如下特征：

  1. 后序中右起第一位3肯定是根结点，我们可以据此找到中序中根结点的位置rootin；
  2. 中序中根结点左边就是左子树结点，右边就是右子树结点，即[左子树结点，根结点，右子树结点]，我们就可以得出左子树结点个数为int left = rootin - leftin;；
  3. 后序中结点分布应该是：[左子树结点，右子树结点，根结点]；
  4. 根据前一步确定的左子树个数，可以确定后序中左子树结点和右子树结点的范围；
  5. 如果我们要前序遍历生成二叉树的话，下一层递归应该是：
    • 左子树：root->left = pre_order(中序左子树序列，后序左子树序列);；
    • 右子树：root->right = pre_order(中序右子树序列，后序右子树序列);。
  6. 每一层递归都要返回当前根结点root；

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  if (!inorder.length || !postorder.length) return null;
  const node = new TreeNode(postorder.pop());
  const index = inorder.indexOf(node.val);
  const leftTree = inorder.slice(0, index);
  const rightTree = inorder.slice(index + 1);
  node.left = buildTree(
    inorder.slice(0, index),
    postorder.slice(0, leftTree.length)
  );
  node.right = buildTree(
    inorder.slice(index + 1),
    postorder.slice(leftTree.length)
  );
  return node;
};

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

思路

经典动态规划问题，新建一个矩阵，记录每一个点可以拿到的最大价值，每一个点能拿到的最大价值是取本身，左边的点，上面的点的最大值。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxValue = function (grid) {
  let m = grid.length;
  let n = grid[0].length;
  const maxGrid = new Array(m);
  for (let i = 0; i < maxGrid.length; i++) {
    maxGrid[i] = new Array(n);
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let num1 = i - 1 < 0 ? -1 : maxGrid[i - 1][j] + grid[i][j];
      let num2 = j - 1 < 0 ? -1 : maxGrid[i][j - 1] + grid[i][j];
      maxGrid[i][j] = Math.max(grid[i][j], num1, num2);
    }
  }
  return maxGrid[m - 1][n - 1];
};