# 递归法 + 前序遍历
def preorderTraversalRecursion(root: TreeNode):
res = []
def tra(root: TreeNode):
if root is None:
return
# 中序遍历和后序遍历只需要修改以下的顺序即可；
res.append(root.val)
res.append(tra(root.left))
res.append(tra(root.right))
tra(root)
return res
迭代法
# 迭代法 + 前序遍历
def preorderTraversalIterate(root: TreeNode):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res
# 迭代法 + 后序遍历
# 和前序代码很像，最后进行反序即可；
def postorderTraversalIterate(root: TreeNode):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res[::-1]
# 迭代法+ 中序遍历
# 核心在于先找到最左node，然后依次append
def inorderTraversalIterate(root: TreeNode):
if not root:
return []
res = []
stack = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
层序遍历
def levelOrder(root: TreeNode):
result = []
if not root:
return []
que = deque([root])
while que:
size = len(que)
res = []
for _ in range(size):
cur = que.popleft()
res.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
result.append(res)
return result
递归法
# 递归法
def recursionOrder(root: TreeNode):
res = []
def helper(root, depth):
if not root:
return []
if len(res) == depth:
res.append([])
res[depth].append(root.val)
if root.left:
helper(root.left, depth + 1)
if root.right:
helper(root.right, depth + 1)
helper(root, 0)
return res
