前言

• 小涛啊小涛，你不能就这么荒废学习安逸享乐！工作找不到啦！

104. 二叉树的最大深度 - 力扣（LeetCode）

• 递归

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

• 层序遍历

  • class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root: return 0q = deque()q.append(root)max_depth = 0  # 最大深度while q:for i in range(len(q)):cur = q.popleft()if cur.left: q.append(cur.left)if cur.right: q.append(cur.right)max_depth += 1  # 遍历完一层，最大深度+1return max_depth

 226. 翻转二叉树 - 力扣（LeetCode）

• 递归

  • # 后序遍历
    class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: returnleftTree = self.invertTree(root.left)        # 左rightTree = self.invertTree(root.right)      # 右root.left, root.right = rightTree, leftTree  # 中return root
    # 先序遍历
    class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: returnroot.left, root.right = root.right, root.left  # 中self.invertTree(root.left)                     # 左self.invertTree(root.right)                    # 右return root

•  迭代

  • # 前序遍历
    class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: returnst = [root]while st:cur = st.pop()cur.left, cur.right = cur.right, cur.left  # 中if cur.right: st.append(cur.right)         # 右if cur.left: st.append(cur.left)           # 左return root# 层序遍历
    class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: returnq = deque()q.append(root)while q:for i in range(len(q)):cur = q.popleft()if cur.left: q.append(cur.left)if cur.right: q.append(cur.right)cur.left, cur.right = cur.right, cur.left  # 交换return root

101. 对称二叉树 - 力扣（LeetCode） 

• 递归法

  • class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truedef dfs(left, right):if not left and not right:  # 00，都为空return Trueelif not (left and right):  # 01和10，一个为空return Falseelif left.val != right.val:  # 值不相等return False# 左左右右 and 左右右左return dfs(left.left, right.right) and dfs(left.right, right.left)return dfs(root.left, root.right)

• 迭代

  • class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root or not(root.left or root.right):  # root空或者左右为空return True# 用队列保存结点q = [root.left, root.right]while q:# 取出两个结点比较left = q.pop(0)right = q.pop(0)# 都为空则继续，有一个为空或者不对称就返回falseif not (left or right):continueelif not (left and right):return Falseelif left.val != right.val:return False# 下次比较左左右右q.append(left.left)q.append(right.right)# 下下次比较左右右左q.append(left.right)q.append(right.left)# 如果整个队列遍历完了说明完全对称return True

 后言

• 这一整天二叉树的，真的学累了，脑子都要叉开了......玩儿去咯