代码随想录算法训练营第15天
翻转二叉树
https://leetcode.cn/problems/invert-binary-tree/description/
翻转二叉树代码随想录
https://programmercarl.com/0226.翻转二叉树.html
对称二叉树题
https://leetcode.cn/problems/symmetric-tree/
对称二叉树代码随想录
https://programmercarl.com/0101.对称二叉树.html#其他语言版本
二叉树最大深度题
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
二叉树最大深度代码随想录
https://programmercarl.com/0104.二叉树的最大深度.html
二叉树最小深度题
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
二叉树最小深度代码随想录
https://programmercarl.com/0111.二叉树的最小深度.html
翻转二叉树
题目
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
重点
- 递归法：正常模拟
- 迭代法：栈前序遍历交换 在node处理时 交换
- 层序遍历法：每个node交换子节点
题解代码
递归法
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.right = left
root.left = right
return root
统一迭代法
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
st = []
res = []
if not root:
return root
else:
st.append(root)
while st:
node = st.pop()
if node:
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
st.append(node)
st.append(None)
else:
node = st.pop()
node.right,node.left = node.left,node.right
return root
层序遍历法
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = collections.deque()
res = []
if not root:
return root
else:
queue.append(root)
while queue:
for i in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
node.right,node.left = node.left,node.right
return root
对称二叉树
题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
重点
- 不是左右子节点完全相同；
- 递归法：compare函数 判断外侧和内侧是否相同；
- 迭代法：遍历：左右-右左；左左-右右；两组分别对比；
- 层序遍历法：1.个数为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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
else:
return self.compare(root.right,root.left)
def compare(self,right,left):
if not right and left: return False
elif not left and right: return False
elif not right and not left: return True
elif right.val != left.val: return False
outside = self.compare(right.right,left.left)
inside = self.compare(right.left,left.right)
return outside and inside
迭代法——队列
# 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
que = collections.deque()
que.append(root.left)
que.append(root.right)
while que:
left = que.popleft()
right = que.popleft()
if left and not right:
return False
elif right and not left:
return False
elif not right and not left:
continue
elif right.val!=left.val:
return False
que.append(left.right)
que.append(right.left)
que.append(right.right)
que.append(left.left)
return True
迭代法——队列和栈没区别
# 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
st = []
st.append(root.left)
st.append(root.right)
while st:
left = st.pop()
right = st.pop()
if left and not right:
return False
elif right and not left:
return False
elif not right and not left:
continue
elif right.val!=left.val:
return False
st.append(left.right)
st.append(right.left)
st.append(right.right)
st.append(left.left)
return True
层序遍历法
# 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
que = collections.deque([root.left,root.right])
while que:
if len(que)%2!=0:
return False
line = []
for i in range(len(que)):
node = que.popleft()
if node:
line.append(node.val)
que.append(node.left)
que.append(node.right)
else:
line.append(None)
if line!=line[::-1]:
return False
return True
二叉树最大深度
题目
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
重点
- 层序遍历法：所有层数的长度；
- 递归法：如果有子节点，选最大的即可
题解代码
递归法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
层序遍历法
# 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:
queue = collections.deque()
res = []
if not root:
return len(res)
else:
queue.append(root)
while queue:
line = []
for i in range(len(queue)):
node = queue.popleft()
line.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(line)
return len(res)
111. 二叉树的最小深度
题目
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
重点
- 递归法：不能直接用min，需要考虑子节点为空节点的情况
- 层序遍历法 ：记录叶子节点的深度+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:
if not root:
return 0
elif not root.right or not root.left:
return 1+max(self.minDepth(root.right),self.minDepth(root.left))
else:
return 1+min(self.minDepth(root.right),self.minDepth(root.left))
层序遍历法
# 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:
queue = collections.deque()
res = []
if not root:
return len(res)
else:
queue.append(root)
while queue:
line = []
for i in range(len(queue)):
node = queue.popleft()
line.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if (not node.right) and (not node.left):
return len(res)+1
res.append(line)