# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
（一）二叉树的中序遍历
递归：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
if root:
res+=self.inorderTraversal(root.left)
res.append(root.val)
res+=self.inorderTraversal(root.right)
return res
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)注：
1. 类中方法的自我调用
2. Python中list可以直接相加得到新的list：
ls1 = [1,2,3]
ls2 = [4,5,6]
print(ls1+ls2)迭代：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# 迭代解法
p = root
res = []
stack = []
while p or stack:
if p:
stack.append(p)
p = p.left
else:
tmp = stack.pop()
res.append(tmp.val);
p = tmp.right
return res
（二）二叉树的先序（前序）遍历
递归：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
‘‘‘递归解法‘‘‘
p =root
res = []
if p!=None:
res.append(p.val)
res += self.preorderTraversal(p.left)
res += self.preorderTraversal(p.right)
return res迭代：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
‘‘‘迭代解法‘‘‘
p = root
res = []
stack = []
while p or stack:
if p:
res.append(p.val)
stack.append(p)
p = p.left
else:
temp = stack.pop()
p = temp.right
return res（三）二叉树的后序遍历
递归：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
p = root
res = []
if p:
res += self.postorderTraversal(p.left)
res += self.postorderTraversal(p.right)
res.append(p.val)
return res
已有详细解释说明，不再说明。
迭代1：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
‘‘‘先序遍历思想实现后续遍历‘‘‘
p = root
#res = []
stack = []
stack2 = []
while p or stack:
if p:
stack2.append(p.val)
stack.append(p)
p = p.right
else:
temp = stack.pop()
p = temp.left
return stack2[::-1]
迭代2：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
‘‘‘后序遍历双指针迭代算法‘‘‘
if not root: # 需要判断是否为空
return []
stack = []
res = []
prev = None
curr = None
stack.append(root)
while stack:
curr = stack[-1]
if prev==None or prev.left==curr or prev.right==curr:
if curr.left!=None:
stack.append(curr.left)
elif curr.right!=None:
stack.append(curr.right)
elif prev == curr.left:
if curr.right!=None:
stack.append(curr.right)
else:
res.append(curr.val)
stack.pop() # 需要弹出
prev = curr
return res
（四）二叉树的层次遍历
采用队列组织结构
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = []
res = []
p = root
queue.append(p)
while queue:
temp = queue.pop(0)
res.append(temp.val)
if temp.left!=None:
queue.append(temp.left)
if temp.right!=None:
queue.append(temp.right)
return res二叉树遍历python3代码（先序、中序、后序、层次）（递归、非递归）
原文：https://www.cnblogs.com/ACStrive/p/11222390.html