代码随想录算法训练营day11（二叉树）

翻转二叉树

• https://leetcode.cn/problems/invert-binary-tree/description/

思路

• 采用递归的思路
• 可以前序遍历和后序遍历，不能使用中序遍历

# 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 invert(self, cur):if not cur:return curcur.left, cur.right = cur.right, cur.left     # 中self.invert(cur.left)    # 左self.invert(cur.right)   # 右def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.invert(root)return root

对称二叉树

• https://leetcode.cn/problems/symmetric-tree/description/

思路

• 使用递归，后序遍历
• 判断一边的左孩子是否等于另一边的右孩子，一边的右孩子是否等于另一边的左孩子

# 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 symmetric(self,left,right):if left and not right:return Falseelif not left and right:return Falseelif not left and not right:return Trueelif left.val != right.val:return Falseres1 = self.symmetric(left.left, right.right)res2 = self.symmetric(left.right, right.left)res = True if res1 and res2 else False   return resdef isSymmetric(self, root: Optional[TreeNode]) -> bool:if self.symmetric(root.left, root.right):return Trueelse:return False

二叉树的最大深度

• https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

思路

• 使用递归
• 后序遍历的思想

# 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:height = 1cur = rootif not cur:return 0leftHeight = self.maxDepth(cur.left)    # 左rightHeight = self.maxDepth(cur.right)  # 右height = height + max(leftHeight, rightHeight)   # 中return height