代码随想录算法训练营第十四天|226.翻转二叉树|101. 对称二叉树|104.二叉树的最大深度|111.二叉树的最小深度
226.翻转二叉树
递归三部曲：
1 确定递归函数的参数和返回值
2 确定终止条件
3 确定单层递归的逻辑
# 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 not root:
return None
root.left,root.right=root.right,root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
|101. 对称二叉树
# 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 not root:
return True
return self.compare(root.left,root.right)
def compare(self,left,right):
if left==None and right==None:
return True
elif left==None and right!=None:
return False
elif left!=None and right==None:
return False
elif left.val!=right.val:
return False
#注意不要判断左右相等就返回true，需要递归到最后
outside=self.compare(left.left,right.right)
inside=self.compare(left.right,right.left)
return (outside and inside)
|104.二叉树的最大深度
确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
确定终止条件：如果为空节点的话，就返回0，表示高度为0。
确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加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 maxDepth(self, root: Optional[TreeNode]) -> int:
return self.depth(root)
def depth(self,root):
if not root:
return 0
left=self.depth(root.left)
right=self.depth(root.right)
dep=1+max(left,right)
return dep
|111.二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
# 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:
return self.getDepth(root)
def getDepth(self,root):
if not root:
return 0
leftdepth=self.getDepth(root.left)
rightdepth=self.getDepth(root.right)
if root.left==None and root.right!=None:
return 1+rightdepth
if root.left!=None and root.right==None:
return 1+leftdepth
return 1+min(rightdepth,leftdepth)