226. 翻转二叉树

226. 翻转二叉树https://leetcode.cn/problems/invert-binary-tree/1.昨天忘了声明，如果都用C的话，我大概率写不完，所以思路方面，我可能考虑用pyhon先写，后续会用文心一言转换成C

2.这里可以直接用层序遍历的写法写出来，但是卡哥说要掌握递归

# 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 not root:
            return root
        from collections import deque
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def traver(root):
            if not root:
                return None
            root.left, root.right = root.right, root.left
            traver(root.left)
            traver(root.right)
        traver(root)
        return root

101. 对称二叉树

101. 对称二叉树https://leetcode.cn/problems/symmetric-tree/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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        from collections import deque
        queue = deque()
        queue.append(root.left)
        queue.append(root.right)
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            if not node1 and not node2:
                continue
            if not node1 or not node2 or node1.val != node2.val:
                return False
            queue.append(node1.left)
            queue.append(node2.right)
            queue.append(node1.right)
            queue.append(node2.left)
        return True

# 递归
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left, root.right)

    def compare(self, left, right):
        if not left and right:
            return False
        if left and not right:
            return False
        if not left and not right:
            return True
        if left.val != right.val:
            return False
        outSide = self.compare(left.left, right.right)
        inSide = self.compare(left.right, right.left)
        return outSide and inSide

104.二叉树的最大深度

104. 二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/1.迭代：可以用层序遍历直接做，在每次遍历之前计数加一即可

2.递归：用递归法的话，需要先选择一个遍历方法

# 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:
        res = 0
        if not root:
            return res
        from collections import deque
        queue = deque()
        queue.append(root)
        while queue:
            res += 1
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res
        

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def traver(root):
            if not root:
                return 0
            left = traver(root.left)
            right = traver(root.right)
            res = 1 + max(left, right)
            return res
        return traver(root)

111.二叉树的最小深度

111. 二叉树的最小深度https://leetcode.cn/problems/minimum-depth-of-binary-tree/1.这里层序直接使用上一题的代码，然后在推出节点时，加一个判断，当该节点时叶子节点，直接返回即可。

2.这里递归的思路是有点问题

# 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:
        res = 0
        if not root:
            return res
        from collections import deque
        queue = deque()
        queue.append(root)
        while queue:
            res += 1
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                if not node.left and not node.right:
                    return res
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        def getres(root):
            if not root:
                return 0
            dleft = getres(root.left)
            dright = getres(root.right)
            if not root.left and root.right:
                return 1 + dright
            if root.left and not root.right:
                return 1 + dleft
            res = 1 + min(dleft, dright)
            return res
        return getres(root)