相似题目：
- 【LeetCode】572. 另一个树的子树
- 【LeetCode】104. 二叉树的最大深度【简单】
- 【LeetCode】110. 平衡二叉树
- 【LeetCode】297. 二叉树的序列化与反序列化【困难】
- 【LeetCode】226.翻转二叉树
- 【LeetCode】235. 二叉搜索树的最近公共祖先
LeetCode 原题地址
7. 144. 二叉树的前序遍历
8. 94. 二叉树的中序遍历
9. 145. 二叉树的后序遍历
10. 102. 二叉树的层序遍历
1. 递归（前、中、后序）
class TreeNode: # 树的节点
def __init__(self,x):
self.val = x
self.left = None
self.right = None
class OperationTree():
def __init__(self, data_list): # 把输入的列表初始化为可迭代对象
self.dataIter = iter(data_list)
def createTree(self, root = None): # 必须补充一句 默认参数root = None 不然会参数数量不匹配
""" 新建一颗树 """
next_data = next(self.dataIter) # 步进获取下一个元素
if next_data == '#': # "#" 号表示叶节点，在程序中用 None 代替 "#" 号
root = None
else: # 是根节点，它还有孩子节点，所以继续创建Node
root = TreeNode(next_data) # 实例化对象（类似于struct）
root.left = self.createTree(root.left)
root.right = self.createTree(root.right)
return root
def preorderTraversal(self, root: TreeNode) -> List[int]:
""" 前序遍历 递归"""
ans = []
def helper(root):
if not root:
return
ans.append(root.val) # 前序遍历，root -> left -> right
helper(root.left)
helper(root.right)
helper(root)
return ans
def inorderTraversal(self, root: TreeNode) -> List[int]:
""" 中序遍历 递归"""
ans = []
def helper(root):
if not root:
return
helper(root.left)
ans.append(root.val) # 中序遍历，left -> root -> right
helper(root.right)
helper(root)
return ans
def postorderTraversal(self, root: TreeNode) -> List[int]:
""" 后序遍历 递归"""
ans = []
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
ans.append(root.val) # 后序遍历，left -> right -> root
helper(root)
return ans
def printTree(self):
""" 综合打印"""
print("递归 前序遍历：", end=" ")
preOrder = self.preorderTraversal(root)
print(preOrder, '\n')
print("递归 中序遍历：", end=" ")
inOrder = self.inorderTraversal(root)
print(inOrder,'\n')
print("递归 后序遍历：", end=" ")
postOrder = self.postorderTraversal(root)
print(postOrder, '\n')
if __name__ == '__main__':
data = 'abd#g###ce##fh###'
#data = [1,2,'#','#',3,'#','#']
newTree = OperationTree(data)
root = newTree.createTree()
newTree.printTree()
""" 递归 前序遍历： ['a', 'b', 'd', 'g', 'c', 'e', 'f', 'h'] 递归 中序遍历： ['d', 'g', 'b', 'a', 'e', 'c', 'h', 'f'] 递归 后序遍历： ['g', 'd', 'b', 'e', 'h', 'f', 'c', 'a'] """
2. 迭代（前、中、后、层序）
class TreeNode: # 树的节点
def __init__(self,x):
self.val = x
self.left = None
self.right = None
class OperationTree():
def __init__(self, data_list): # 把输入的列表初始化为可迭代对象
self.dataIter = iter(data_list)
def createTree(self, root = None): # 必须补充一句 默认参数root = None 不然会参数数量不匹配
""" 新建一棵树 """
next_data = next(self.dataIter) # 步进获取下一个元素
if next_data == '#': # "#" 号表示叶节点，在程序中用 None 代替 "#" 号
root = None
else: # 是根节点，它还有孩子节点，所以继续创建Node
root = TreeNode(next_data) # 实例化对象（类似于struct）
root.left = self.createTree(root.left)
root.right = self.createTree(root.right)
return root
def preorderTraversal(self, root: TreeNode) -> List[int]:
"""前序遍历 迭代"""
# T = root # 可以用临时变量，以防修改原始数据
stack = []
preData = []
while (root or stack): # 树不空，或者堆栈不空
while root: # 只要节点不是 None，即树不空，就一直把节点压入堆栈，并且一直往左走到死胡同里，结束循环
stack.append(root) # 入栈（第一次碰到）
preData.append(root.val) # 前序遍历是第一次碰到就输出
root = root.left # 一直往左走，并一直压入堆栈
# 上述压栈循环结束，跳出
if stack:
root = stack.pop() # 出栈（第二次碰到，中序遍历就是放在这里之后），开始往回走，pop出 root
root = root.right # 继续往右走
return preData
def inorderTraversal(self, root: TreeNode) -> List[int]:
""" 中序遍历 迭代 1. 遇到一个节点，将其压入堆栈，并去遍历它的左子树 2. 当左子树遍历结束后，从栈顶弹出这个节点并访问它 3. 然后按照其右指针再去中序遍历该节点的右子树 """
T = root
stack = []
inData = []
while (T or stack):
while T:
stack.append(T) # 第一次碰到
T = T.left
if stack:
T = stack.pop() # pop 出 root，即第二次碰到
inData.append(T.val) # 第二次碰到之后输出
T = T.right
return inData
def postorderTraversal(self, root: TreeNode) -> List[int]:
""" 后序遍历 迭代 和前序遍历的区别是把 left/right 互换，最后再把获得的数据逆序输出"""
T = root
stack = []
postData = []
while (T or stack):
while T:
stack.append(T)
postData.append(T.val)
T = T.right # 先 right，再 left
if stack:
T = stack.pop()
T = T.left
return postData[::-1] # 最后逆序输出
def levelOrder_1D(self, root: TreeNode) -> List[List[int]]:
""" 层序遍历 迭代 BFS 输出一维列表 [3,9,20,null,null,15,7] => [3,9,20,15,7]"""
T = root
if not T:
return
queue = []
levelData = []
queue.append(T)
while queue:
T = queue.pop(0) # 取出队首元素
levelData.append(T.val) # 并且输出
if T.left:
queue.append(T.left)
if T.right:
queue.append(T.right)
return levelData
def levelOrder_2D(self, root: TreeNode) -> List[List[int]]:
""" 层序遍历 迭代 BFS 输出二维列表 [3,9,20,null,null,15,7] => [[3],[9,20],[15,7]] 1. 从队列中取出一个元素 2. 访问该元素所指的节点 3. 若该节点所指的节点左右孩子非空，则将其左右孩子的指针顺序入队 """
T = root
if not T:
return[]
queue = []
ans = [] # 最终二维列表答案
level = [] # 每一层
queue.append(T) # 入队
curCount, nextCount = 1, 0 # 当前层节点数、下一层节点数
while queue:
T = queue.pop(0) # 出队
level.append(T.val)
curCount = curCount - 1 # 每输出一个当前层的节点，把当前层节点数减去 1
if T.left: # 左子树
queue.append(T.left)
nextCount = nextCount + 1 # 每添加一个下一层节点，则把下一层节点数加 1
if T.right: # 右子树
queue.append(T.right)
nextCount = nextCount + 1
if curCount == 0: # 当前层节点数量为 0，表示当前层已经输出完毕，需要访问下一层
ans.append(level) # 一层一层添加
curCount = nextCount
nextCount = 0 # 置零，等待重新计数
level = []
return ans
def printTree(self):
""" 综合打印"""
print("迭代 前序遍历：", end=" ")
print(self.preorderTraversal(root))
print("迭代 中序遍历：", end=" ")
print(self.inorderTraversal(root))
print("迭代 后序遍历：", end=" ")
print(self.postorderTraversal(root))
print("迭代 层序遍历1D：", end=" ")
print(self.levelOrder_1D(root))
print("迭代 层序遍历2D：", end=" ")
print(self.levelOrder_2D(root))
if __name__ == '__main__':
data = 'abd#g###ce##fh###'
# data = ''
newTree = OperationTree(data)
root = newTree.createTree()
newTree.printTree()
""" 【例子】 abd#g###ce##fh### 先序遍历: a b d g c e f h 中序遍历: d g b a e c h f 后序遍历: g d b e h f c a 迭代 层序遍历1D： ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'] 迭代 层序遍历2D： [['a'], ['b', 'c'], ['d', 'e', 'f'], ['g', 'h']] """
京公网安备 11010502036488号