层序遍历
1、迭代法，使用队列
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if root is None:
return res
queue = [root]
while queue:
n = len(queue)
tmp = []
for i in range(n):
node = queue.pop(0)
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res
2、递归
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
levels = []
if root is None:
return levels
self.helper(root, 0, levels)
return levels
def helper(self, node, level, levels):
if not node:
return
if level == len(levels):
levels.append([])
levels[level].append(node.val)
self.helper(node.left, level+1, levels)
self.helper(node.right, level+1, levels)
226.翻转二叉树
1、递归前序遍历
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return root
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
2、前序遍历的统一写法
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if node:
if node.right:
stack.append(node.right) # 右
if node.left:
stack.append(node.left) # 左
# 需要处理的节点
stack.append(node) # 中
stack.append(None) # 作标记
else:
# 处理节点
node = stack.pop()
node.left, node.right = node.right, node.left
return root
101.对称二叉树 2
1、递归法
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
return self.compare(root.left, root.right)
def compare(self, left, right):
if not left and not right: # 一层一层排除
return True
if not (left and right):
return False
if left.val != right.val:
return False
return self.compare(left.left, right.right) and self.compare(left.right, right.left)