【刷题DAY18】513, 112, 113, 106, 105.md

发表于 | 分类于

0x00 513. 找树左下角的值

题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/

0x1 看到题目的第一想法

  • 层序遍历，🉑️

0x2 自己实现过程中遇到哪些困难

  • 层序遍历 漏
  • 递归
    • python全局变量
    • 递归函数里面需要用nonlocal进行声明

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 递归 + 回溯
  • MaxDepth用来记录最大深度，result记录最大深度最左节点的数值。
  • 递归
    • 函数输入输出
      • 根节点，当前节点的深度
    • 终止条件
      • 到叶子节点就结束
      • 且在叶子节点需要多做一步，更新MaxDepth和result
    • 当前逻辑
      • 先左子树再右子树，一定要左优先，这样保证终止那里是存的最深的最左的叶子

0x5 今日收获，记录一下自己的学习时长

  • 1.5h

112. 路径总和

题目链接：https://leetcode.cn/problems/path-sum/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 函数参数用的sum，条件返回有问题，返回null，没有结果
  • 看了解析之后，自己写还是反回null，这里是有do sth!!我写的时候漏了，只有直接返回这项，都失败反而没有返回

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 不用sum正着来，用target减去节点数反着来

0x5 今日收获，记录一下自己的学习时长

  • 路径总和
    • 判断能否找到一条符合条件的路径，找到了就提前返回
    • 递归 + 隐形回溯
  • 注意do sth
    • 还有一个return False
      -如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
  • 1.5h

113. 路径总和ii

题目链接：https://leetcode.cn/problems/path-sum-ii/

0x1 看到题目的第一想法

  • 找到符合条件的所有路径

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

0x5 今日收获，记录一下自己的学习时长

  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。 (113.路径总和ii)
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 (36. 二叉树的最近公共祖先)
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。 (112.路径总和)
  • 1.5h

106 & 105

  1. 从前序与中序遍历序列构造二叉树: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
  2. 从中序与后序遍历序列构造二叉树: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

    0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间

0x5 今日收获，记录一下自己的学习时长

  • 2h

待重点复习

513, 112, 113, 106, 105

总结

  • 找树左下角的值
    • 递归 + 回溯
  • 路径总和
    • 递归函数返回值
      • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。 (113.路径总和ii)
      • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 (36. 二叉树的最近公共祖先)
    • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。 (112.路径总和)
  • 从前(后)序与中序构造二叉树
    • 六步