请假

这两天喉咙发炎, 头晕眼花, 只能写一些简单题了

二叉树的中序遍历

# 递归, 非常简单而且常用
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node):
            # 访问到左子树的末尾. 返回
            if not node:
                return 
            # 先访问左子树
            dfs(node.left)
            # 左子树访问完, 访问根节点
            ans.append(node.val)
            # 然后访问右子树
            dfs(node.right)
        dfs(root)
        return ans

# 迭代(维护一个栈)
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans, stack = [], []
        cur = root
        # 当前节点不为空, 则右子树不为空或者为初始节点, stack不为空而cur为空, 则是右子树是空的, 但是还没有访问完所有节点
        while cur or stack:
            while cur:
                # 一路向左
                stack.append(cur)
                cur = cur.left
            # 出栈
            cur = stack.pop()
            ans.append(cur.val)
            cur = cur.right

        return ans          

二叉树的最大深度

# 显式存储当前深度
# 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:
        cnt = 1
        if not root:
            return 0
        q = deque([(root, 1)])
        while q:
            cur, cur_cnt = q.pop()
            cnt = max(cnt, cur_cnt)
            if cur.left:
                q.append((cur.left, cur_cnt + 1))
            if cur.right:
                q.append((cur.right, cur_cnt + 1))
        return cnt
# 层序遍历
# 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:
        cnt = 0
        if not root:
            return 0
        q = deque([root])
        while q:
            for _ in range(len(q)):
                # 注意要popleft才是弹出当前层
                cur = q.popleft()
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            cnt += 1
        return cnt

翻转二叉树

# 递归写法
# 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
		# 一路往下到最后一层然后开始子树翻转
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

对称二叉树

# 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
      
        # di'gui
        def dfs(l, r):
            if not l and not r:
                return True
            if not l or l not r:
                return False
            if l.val != r.val:
                return False
            return dfs(l.left, r.right) and dfs(l.right, r.left)
      
        return dfs(root.left, root.right)