【刷题DAY14】层序遍历10, 226, 101.md

0x00 层序遍历10

题目链接：

1. 二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/
2. 二叉树的层序遍历 II https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
3. 二叉树的右视图 https://leetcode.cn/problems/binary-tree-right-side-view/
4. 二叉树的层平均值 https://leetcode.cn/problems/average-of-levels-in-binary-tree/
5. N叉树的层序遍历 https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
6. 在每个树行中找最大值 https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
7. 填充每个节点的下一个右侧节点指针 https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
8. 填充每个节点的下一个右侧节点指针II https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
9. 二叉树的最大深度 https://leetcode.cn/problems/maximum-depth-of-binary-tree/
10. 二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/

0x1 看到题目的第一想法

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

• 429 N叉树的层序遍历。
• 116 填充每个节点的下一个右侧节点指针

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

• https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

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

class Solution:
    """二叉树层序遍历迭代解法"""

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results = []
        if not root:
            return results
        
        from collections import deque
        que = deque([root])
        
        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        return results

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

• 429 层序遍历
  • que.extend(cur.children)
• 填充右节点

  if i == n - 1:
       break
  node.next = queue[0]

• 1h

---

226. 翻转二叉树

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

0x1 看到题目的第一想法

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

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

• https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

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

• 使用前序遍历或后序遍历，不可以使用中序遍历，某些节点会反转两次
• 遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果
• 递归
  • 明确函数定义
    • 这个函数是干什么的，输入是什么，会有什么样的输出
  • 确定递归终止条件
  • 当前节点要进行的操作

    def invert(root: Optional[TreeNode]):
                # 1.函数定义，明确输入是什么，输出是什么
                # 反转左右子孩子
                # 输入：根结点
                # 输出：反转了根结点的左右孩子之后的
                # 2. 递归结束条件
                if not root:
                    return root
                # 3. 看单个节点的逻辑。 
                # 前序遍历，先处理当前节点，在处理左右孩子
                root.left, root.right = root.right, root.left
                invert(root.left)
                invert(root.right)
                return root
            root = invert(root)
            return root

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

• 翻转二叉树
  • 前序遍历或后序遍历，翻转节点的当前孩子节点，再把左右孩子也放进去递归翻转
• 1h

---

101. 对称二叉树

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

0x1 看到题目的第一想法

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

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

• https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

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

• 判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
  • 比较外侧（left.left和right.right）和内侧（left.right和right.left）节点。
• 递归
  • 明确函数定义
    • 这个函数是干什么的，输入是什么，会有什么样的输出
    • 比较当前这个两个子树是不是对称的
    • 输入：两个子树的根节点
    • 输出判断结果
  • 确定递归终止条件
    • 空节点情况
      • 左空右空，返回True
      • 左不空右空，False
      • 左空右不空，True
    • 左右都不空
      • value值都不相等，False
  • 当前节点要进行的操作
    • 左右都不空
      • value值都相等，left的左右孩子放进去递归，如果为真，则继续把right的左右孩子放进去递归返回结果

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

• 对称二叉树
  • 递归
• 1h

待重点复习

429, 116, 226, 101

总结

• 层序遍历
  • 队列
• 翻转二叉树
  • 递归
    • 前序
• 对称二叉树
  • 递归