代码随想录算法训练营day18 | 102.二叉树的层序遍历、226.翻转二叉树、101. 对称二叉树

102.二叉树的层序遍历

迭代法

层序遍历使用队列，同时记录每层的个数

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:res = []if not root:return resqueue = collections.deque()queue.append(root)while queue:size = len(queue)tmp = []for _ in range(size):node = queue.popleft()tmp.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(tmp)return res

递归法

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:result = []self.order(root, result, 0)return resultdef order(self, cur, result, depth):if not cur:returnif len(result) == depth:result.append([])result[depth].append(cur.val)self.order(cur.left, result, depth+1)self.order(cur.right, result, depth+1)

226.翻转二叉树

递归法

递归时，中序遍历会重复翻转部分，本题只能使用前序遍历和后序遍历

能够在看题解之前写出来，有进步

class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:# 前序遍历if not root:returnroot.left, root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return rootclass Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:# 后序遍历if not root:returnself.invertTree(root.left)self.invertTree(root.right)root.left, root.right = root.right, root.leftreturn root

101. 对称二叉树

递归法

class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truereturn self.symmetric(root.left, root.right)def symmetric(self, left, right):if (not left and right) or (not right and left):return Falseif not left and not right:return Trueif left.val != right.val:return Falsereturn self.symmetric(left.left, right.right) and self.symmetric(left.right, right.left)