代码随想录算法训练营第十四天|226、翻转二叉树 101、对称二叉树 104、二叉树的最大深度 111、二叉树的最小深度

目录226. 翻转二叉树题目描述解题思路101. 对称二叉树题目描述解题思路104. 二叉树的最大深度题目描述解题思路111. 二叉树的最小深度题目描述解题思路题目描述给你一棵二叉树的根节点root翻转这棵二叉树并返回其根节点。解题思路遍历各个节点交换他们的左右孩子class Solution: def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: cur root def dfs(node): if node is None: return node.right,node.left node.left,node.right dfs(node.left) dfs(node.right) dfs(cur) return root101. 对称二叉树题目描述给你一个二叉树的根节点root 检查它是否轴对称。解题思路对称二叉树此时不是比较左右子树是否完全相同而是判断一个子树镜像翻转是否等于另一个子树借由上题的方法计算翻转二叉树再分别遍历两个子树判断是否相等class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: #左右子树 left_tree root.left right_tree root.right #翻转二叉树 def dfs(node): if node is None: return node.left,node.right node.right,node.left dfs(node.left) dfs(node.right) #翻转右子树 dfs(right_tree) result1 [] result2 [] #遍历两个子树 def dfsearch(node,result): if node is None: result.append(-1) return result.append(node.val) dfsearch(node.left,result) dfsearch(node.right,result) dfsearch(left_tree,result1) dfsearch(right_tree,result2) #判断是否相等 return result1 result2104. 二叉树的最大深度题目描述给定一个二叉树root返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。解题思路层序遍历计算深度也可以直接套用day12的层序遍历返回时返回len(res)class Solution: def maxDepth(self, root: Optional[TreeNode]) - int: queue deque([root]) node root if node is None: return 0 high 0 while queue: size len(queue) for _ in range(size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) high 1 return high111. 二叉树的最小深度题目描述给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明叶子节点是指没有子节点的节点。解题思路最小深度就是层序遍历的灵活应用层序遍历所有节点判断当前节点是否为叶子结点二叉树中一定至少有一个结点为叶子节点找到直接return high 1,因为high是上层深度没有包括当前计算的叶子节点的深度class Solution: def minDepth(self, root: Optional[TreeNode]) - int: high 0 if root is None: return 0 queue deque([root]) while queue: size len(queue) for _ in range(size): node queue.popleft() if node.left is None and node.right is None: return high 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) high 1