代码随想录算法训练营第十四天|leetcode226. 翻转二叉树、leetcode101.对称二叉树、leetcode104.二叉树的最大深度、leetcode111.二叉树的最小深度

1 leetcode226. 翻转二叉树

题目链接：226. 翻转二叉树 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树哔哩哔哩bilibili

自己的思路：之前想过就是使用层序遍历的方法来做这一道题目，后来感觉有一些行不通，就没去尝试，直接看视频，加看别人的代码做的，然后有一种自己很蠢的感觉

1.1 视频后的代码实现

就是左右位置交换进行保存即可

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        root.left,root.right = root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

1.2 小结

1. 主要就是一个思路吧，遇到中间节点进行保存，然后左右节点的位置进行交换，感觉递归我好像在这里第一次理解

2 leetCode101.对称二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树哔哩哔哩bilibili

自己的思路：之前想过就是使用层序遍历的方法来做这一道题目，后来感觉有一些行不通，就没去尝试，直接看视频，加看别人的代码做的，然后有一种自己很蠢的感觉

2.1 看视频后做的方法

思路：

1. 分析问题，这个题目是对称二叉树，首先考虑递归里面的内容，那么进入的是什么序列呢，就是后序排序

2. 确定排序以后，然后判断哪些数据是需要返回的，分析出四种情况，然后再对数据进行迭代，迭代选择的时候，就是看比较的数据是什么，我们比较是不是对称，然后就是由外向内比较

3. 最后就是迭代，返回比较的两个值相不相同

4. 函数调用

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        return self.compare(root.left,root.right)
    def compare(self,left,right):
        if left==None and right !=None:
            return False
        elif left!=None and right == None:
            return False
        elif left==None and right == None:
            return True
        elif left.val != right.val:
            return False
        outside = self.compare(left.left,right.right)
        inside = self.compare(left.right,right.left)
        same = outside and inside
        return same

2.2 小结

1. 这道题有一种，会了以后自己好傻，不会的时候，这是啥的感觉

3 LeetCode104.二叉树的最大深度

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | LeetCode：104.二叉树的最大深度哔哩哔哩bilibili

自己的思路：一点思路，使用前序遍历的方法，然后也有一点左右比较，进行下一层吧

3.1 看视频以后的代码实现

看了视频，觉得其实用高度来求，比深度，更容易一些

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.get_height(root)
​
    def get_height(self,node):
        if node == None:
            return 0
        leftheight = self.get_height(node.left)
        rightheight = self.get_height(node.right)
        max_height = 1+max(leftheight,rightheight)
        return max_height

3.2 小结

1. 这一题里面有一个地方写错了，就是一个类中，他们两个属于同一个级别的，但是第一次缩进了

2. 在函数类别定义函数的时候，需要对其进行一个self

4 leetcode111.二叉树的最小深度

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

文章链接：代码随想录

视频链接：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度哔哩哔哩bilibili

思路：想着将上一道题改一下，没想到报错了，然后就看到了另一种情况，在想如何处理

4.1 看视频后的一部分处理

主要是面对左右有空的情况，学到了学到了，其实可以理解为这个二叉树从头遍历，只需要两边计算即可，哈哈哈哈哈哈

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        return self.depth(root)
    def depth(self,node):
        if node == None:
            return 0
        leftdepth = self.depth(node.left)
        rightdepth = self.depth(node.right)
        if node.left == None and node.right != None:
            return 1+rightdepth
        if node.right == None and node.left != None:
            return 1+leftdepth
        min_dep = 1+min(leftdepth,rightdepth)
        return min_dep

4.2 小结

1. 这个题，就是在一道一道下来后，发现这道题挺简单的，然后尝试自己写了，写通了还理解了

5 今日总结

1. 记录一下第一次因为项目通宵，后来结果我来写了这个题目

2. 递归真的有理解了，老师讲的太清楚了，真的，可能第一次看会有不懂得，但是越看越明了，路越好走