Day 14 卡玛笔记
这是基于代码随想录的每日打卡
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.left
invert(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 root
def invert(node):
if node==None:
return
invert(node.left)
node.left,node.right=node.right,node.left
invert(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 True
def compare(left,right):
# 递归终止条件
if left==None and right:
return False
if left and right==None:
return False
if left==None and right==None:
return True
if 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 0
leftheight=getdepth(node.left)
rightheight=getdepth(node.right)
# 为什么是1加最大值？
# 当节点为叶子节点时，叶子节点的左右孩子返回1+0=1，也就是说叶子节点的高度为1
height=1+max(leftheight,rightheight)
# 返回高度给上一层
return height
return 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 = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
def maxdepth(node):
if node==None:
return 0
max_depth=1
for child in node.children:
max_depth=max(max_depth,maxdepth(child)+1)
return max_depth
return 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)+1
return height
return getmin(root)
运行结果
有问题欢迎评论或私信