目录
今日任务：
- 二叉树的层序遍历
- LeetCode226 翻转二叉树
- LeetCode101 对称二叉树
资料来源：
1 二叉树的层序遍历
题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围 [0, 2000] 内
- -1000 <= Node.val <= 1000
这道题同107、199、637、429、515、116、117、104、111，都是层序遍历和它的各种修改版本。116和117有别的写法，可以利用已经建立的next指针来进行优化。
pythonfrom collections import deque
from typing import Optional, List
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
queue = deque()
result = []
node = root
queue.append(node)
while len(queue) != 0:
size = len(queue)
result_ = []
for _ in range(size):
node = queue.popleft()
result_.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(result_)
return result
2 LeetCode226 翻转二叉树
题目
给你一棵二叉树的根节点 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 = [] 输出：[]
提示：
- 树中节点数目范围在 [0, 100] 内
- -100 <= Node.val <= 100
挨个节点交换左右孩子即可，层序秒了。另外注意，如果要用中序，按照以往的写法，左子树会被翻转两次。处理完左子树，交换左右子树之后，还得翻转左子树才行。
pythonfrom collections import deque
from typing import Optional
# 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 is None:
return None
queue = deque()
node = root
queue.append(node)
while len(queue) != 0:
node = queue.popleft()
temp = node.left
node.left = node.right
node.right = temp
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return root
3 LeetCode101 对称二叉树
题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围 [1, 1000] 内
- -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
一开始是想写迭代的，然后写着写着就一发不可收拾。这个写法同时对根节点的左右子树进行中序和反中序遍历，只要有节点不同就返回False。然后就写成了这样，中间的判断太多了。一开始用层序就好了，那个还好想一些。
python# 我的代码
from collections import deque
from typing import Optional
# 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.right is None and root.left is None:
return True
if not (root.right is not None and root.left is not None):
return False
stack_left = deque()
stack_right = deque()
node = root
stack_left.append(node.left)
stack_right.append(node.right)
while len(stack_left) != 0:
node_left = stack_left.pop()
if len(stack_right) == 0:
return False
node_right = stack_right.pop()
if node_left is None:
node_left = stack_left.pop()
if len(stack_right) == 0:
return False
node_right = stack_right.pop()
if node_right is None:
return False
print(node_left.val)
print(node_right.val)
if node_left.val != node_right.val:
return False
else:
if node_left.right is not None:
stack_left.append(node_left.right)
stack_left.append(node_left)
stack_left.append(None)
if node_left.left is not None:
stack_left.append(node_left.left)
if node_right is None:
return False
if node_right.left is not None:
stack_right.append(node_right.left)
stack_right.append(node_right)
stack_right.append(None)
if node_right.right is not None:
stack_right.append(node_right.right)
if len(stack_right) != 0:
return False
return True
文档给的思路就是，递归的时候同时处理两个节点，本质上还是两边同时遍历。比较的时候同时比较外层和内层。对于左子树和右子树来说，这相当于是左右中和右左中的两种后序遍历。
python# 根据文档思路写的代码 递归版本
from typing import Optional
# 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.left is None and root.right is None:
return True
if not (root.left is not None and root.right is not None):
return False
else:
return self.recursion(root.left, root.right)
def recursion(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
# 递归终止条件
if left is None and right is None:
return True
if not (left is not None and right is not None):
return False
else:
if left.val != right.val:
return False
# 单层递归逻辑
outside = self.recursion(left.left, right.right) # 外层
inner = self.recursion(left.right, right.left) # 内层
return outside and inner
这个写迭代也不是不能写，思路和递归版本是一样的，用队列实现（用栈应该也是一个效果）。
pythonfrom collections import deque
from typing import Optional
# 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.left is None and root.right is None:
return True
if not (root.left is not None and root.right is not None):
return False
else:
queue = deque()
queue.append(root.left)
queue.append(root.right)
while len(queue) != 0:
left = queue.popleft()
right = queue.popleft()
if left is None and right is None:
continue
if not (left is not None and right is not None):
return False
if left.val != right.val:
return False
queue.append(left.left)
queue.append(right.right)
queue.append(left.right)
queue.append(right.left)
return True
总之这道题只要悟到了得左右子树同时进行两种后序遍历就很好写。
所以我是怎么写的那么史山的……
本文作者:御坂19327号
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
目录