这是基于代码随想录的每日打卡
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
递归法（前序、后序）
思路
二叉树的前中后序遍历的操作是将遍历到的节点存进数组，换一步想，将这个操作换成交换左右孩子不就可以了？
代码
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:# 如果根节点为None直接返回if root==None:return root# 递归函数def invert(node):# 空节点直接返回上一层if node==None:return# 交换节点node.left,node.right=node.right,node.leftinvert(node.left)invert(node.right)invert(root)return root# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# if root==None:
# return root
# def invert(node):
# if node==None:
# return
# invert(node.left)
# invert(node.right)
# node.left,node.right=node.right,node.left
# invert(root)
# return root
运行结果
递归法（伪中序）
为什么叫伪中序呢？因为真正的中序是翻转不了二叉树的。中序的遍历顺序的左中右，以下面二叉树为例：
若是中序遍历，第一次翻转时将翻转9和6
第二次遍历将翻转4的左右孩子
下一步就需要翻转4的右孩子，7了，可是第一步我们才刚刚翻转过，所以采用中序遍历会导致乱序，但是我们可以换一步想：将左中右换成左中左的遍历顺序不就可以了吗
代码
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if root==None:return rootdef invert(node):if node==None:returninvert(node.left)node.left,node.right=node.right,node.leftinvert(node.left)invert(root)return root
运行结果
101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
递归法
代码
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:# 没根节点也是对称if root==None:return Truedef compare(left,right):# 递归终止条件if left==None and right:return Falseif left and right==None:return Falseif left==None and right==None:return Trueif left.val != right.val:return False# 递归逻辑bool1=compare(left.left,right.right)bool2=compare(left.right,right.left)return bool1 and bool2# 传入根节点的左后孩子return compare(root.left,root.right)
运行结果
104. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
递归法
# 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:# 这里用的是后序遍历def getdepth(node):if node==None:return 0leftheight=getdepth(node.left)rightheight=getdepth(node.right)# 为什么是1加最大值？# 当节点为叶子节点时，叶子节点的左右孩子返回1+0=1，也就是说叶子节点的高度为1height=1+max(leftheight,rightheight)# 返回高度给上一层return heightreturn getdepth(root)
运行结果
559. N 叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5
代码
"""
# Definition for a Node.
class Node:def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):self.val = valself.children = children
"""class Solution:def maxDepth(self, root: 'Node') -> int:def maxdepth(node):if node==None:return 0max_depth=1for child in node.children:max_depth=max(max_depth,maxdepth(child)+1)return max_depthreturn maxdepth(root)
运行结果
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明： 叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
递归法
求最小深度和求最大深度一样后序遍历就可以了，有些人可能会直接这样的代码：
leftheight=getmin(node.left)
rightheight=getmin(node.right)
height=min(leftheight,rightheight)+1
其实还有这个误区：
代码
# 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 minDepth(self, root: Optional[TreeNode]) -> int:def getmin(node):if node==None:return 0# 当右节点为空，左节点不为空if node.left==None and node.right!=None:return 1+getmin(node.right)# 当左节点不为空，右节点为空if node.left!=None and node.right==None:return 1+getmin(node.left)leftheight=getmin(node.left)rightheight=getmin(node.right)height=min(leftheight,rightheight)+1return heightreturn getmin(root)
运行结果
有问题欢迎评论或私信
