题目简介
今天题目比较直观，就不上题目的简介了，重点是要掌握递归、迭代和集中遍历三种不同的形式。
初见思路
前序遍历： 根、左、右； 中序遍历：左、根、右；后序遍历：左、右、根
i. 迭代式遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
return [root.val] + left + right
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val] + right
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]
结合Python的特性，我们可以这么写很简洁。
ii. 迭代式遍历: 核心是使用栈
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 根结点为空则返回空列表
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# 中结点先处理
result.append(node.val)
# 右孩子先入栈
if node.right:
stack.append(node.right)
# 左孩子后入栈
if node.left:
stack.append(node.left)
return result
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [] # 不能提前将root结点加入stack中
result = []
cur = root
while cur or stack:
# 先迭代访问最底层的左子树结点
if cur:
stack.append(cur)
cur = cur.left
# 到达最左结点后处理栈顶结点
else:
cur = stack.pop()
result.append(cur.val)
# 取栈顶元素右结点
cur = cur.right
return result
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
# 中结点先处理
result.append(node.val)
# 左孩子先入栈
if node.left:
stack.append(node.left)
# 右孩子后入栈
if node.right:
stack.append(node.right)
# 将最终的数组翻转
return result[::-1]
iii. 不使用数据结构的统一迭代法
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st= []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
st.append(node) #中
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right: #添加右节点（空节点不入栈）
st.append(node.right)
st.append(node) #添加中节点
st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
if node.left: #添加左节点（空节点不入栈）
st.append(node.left)
else: #只有遇到空节点的时候，才将下一个节点放进结果集
node = st.pop() #重新取出栈中元素
result.append(node.val) #加入到结果集
return result
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
st.append(node) #中
st.append(None)
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
复盘思路
重点难点
对于面试和日常使用，其实知道递归和迭代法即可，统一迭代是一种可能解但是增加问题的复杂度，属于拔高 。
今日收获
1、二叉树的基本类型
2、 二叉树的前、中、后序遍历
