遍历树状结构的前向和后向方向,一般可以使用递归或者迭代的方式来实现。下面是两种常用的解决方法,包含代码示例:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前向遍历
def preorder_traversal(root):
if root is None:
return
print(root.val) # 访问根节点
preorder_traversal(root.left) # 递归遍历左子树
preorder_traversal(root.right) # 递归遍历右子树
# 后向遍历
def postorder_traversal(root):
if root is None:
return
postorder_traversal(root.left) # 递归遍历左子树
postorder_traversal(root.right) # 递归遍历右子树
print(root.val) # 访问根节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前向遍历
def preorder_traversal(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val) # 访问节点
if node.right:
stack.append(node.right) # 先将右子节点入栈
if node.left:
stack.append(node.left) # 再将左子节点入栈
# 后向遍历
def postorder_traversal(root):
if root is None:
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) # 再将右子节点入栈
result.reverse() # 反转结果列表
for val in result:
print(val) # 访问节点
以上是两种常用的遍历树状结构的前向和后向方向的解决方法,包含了代码示例。具体选择哪种方法取决于实际需求和个人偏好。