【刷题DAY17】110, 257, 404.md

发表于 | 分类于

0x00 110.平衡二叉树

题目链接：https://leetcode.cn/problems/balanced-binary-tree/

0x1 看到题目的第一想法

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

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

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

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
    • 前序遍历
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
    • 只能后序遍历
  • 递归
    • 函数定义
      • 输入：根节点
      • 输出：不是平衡二叉返回-1，是平衡二叉则返回这个节点的深度，1+max{左、右子树深度}
    • 结束条件：不是平衡二叉 直接返回-1
    • 当前逻辑：
      • 判断是否是平衡二叉树，返回结果
        • res = -1 if abs(highleft - highright) > 1 else 1 + max(highleft, highright)

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

  • 求深度
    • 后续遍历
  • 1.5h

257. 二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/

0x1 看到题目的第一想法

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

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

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

  • 二叉树的所有路径
    • 前序遍历加回溯。因为要把路径记录下来，所以涉及到回溯，需要回溯来回退一个路径再进入另一个路径。
    • 隐形回溯
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      class Solution:
          def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
              def dfs(node, path, res):
                  print(1)
                  if not node.left and not node.right:
                      return res.append(path+str(node.val))
                  
                  if node.left:
                      dfs(node.left, path+str(node.val)+'->', res)
                  if node.right:
                      print(path+str(node.val)+'->')
                      dfs(node.right, path+str(node.val)+'->', res)

              if not root:
                  return []
              res = []
              dfs(root, '', res)
              return res

      重点在于path + '->'   
      回溯就隐藏在dfs(node.left, path+str(node.val)+'->', res)中的 path + "->"    每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。

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

  • 保存遍历过的路径
    • 需要用到回溯
    • 隐藏回溯
  • 1.5h

404.左叶子之和

题目链接：https://leetcode.cn/problems/sum-of-left-leaves/

0x1 看到题目的第一想法

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

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

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

  • 判断左叶子，不是二叉树左侧节点
    • 左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
    • 那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
    • 后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。
    • 递归
      • 函数输入输出
        • 输入：根节点
        • 输出：左叶子节点树之和
      • 结束条件
        • 空节点，返回0
        • 叶子节点，返回0
      • 当前逻辑
        • 左子树的左侧叶子之和
        • 右子树的左侧叶子之和
        • do sth：当前这个节点是不是左叶子的父节点，如果是的话，需要更新左叶子值（因为这个点如果左侧叶子的父节点，那么前面一个递归调用求左子树的left结果必定是0，这里就直接覆盖left的值了）。求当前当前根节点的左叶子之和，并返回。
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          class Solution:
              def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
                  
                  # 根节点
                  if not root:
                      return 0
                  # 叶子节点
                  if not root.left and not root.right:
                      return 0
                  # 
                  left = self.sumOfLeftLeaves(root.left)
                  right = self.sumOfLeftLeaves(root.right)
                  if(root.left and not root.left.left and not root.left.right):
                      left = root.left.val
                  return left + right

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

  • 左叶子之和
    • 明确左叶子定义以及当前逻辑
    • 仅凭当前节点是无法判断是否为左叶子的
  • 1.5h

待重点复习

110, 257, 404

总结

  • 求深度
    • 后续遍历
  • 二叉树的所有路径
    • 前序遍历，回溯
  • 左叶子和
    • 仅凭当前节点是无法判断是否为左叶子的