本文主要是介绍代码随想录算法训练营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)
这篇关于代码随想录算法训练营day18 | 102.二叉树的层序遍历、226.翻转二叉树、101. 对称二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!