在Python中,可以使用遞歸或者迭代的方式來實現二叉樹的遍歷。以下是常見的三種二叉樹遍歷方式的代碼示例:
遞歸實現:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root):
if root is None:
return []
result = [root.val]
result += preorderTraversal(root.left)
result += preorderTraversal(root.right)
return result
迭代實現:
def preorderTraversal(root):
if root is None:
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(root):
if root is None:
return []
result = []
result += inorderTraversal(root.left)
result.append(root.val)
result += inorderTraversal(root.right)
return result
迭代實現:
def inorderTraversal(root):
if root is None:
return []
stack = []
result = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
result.append(node.val)
root = node.right
return result
遞歸實現:
def postorderTraversal(root):
if root is None:
return []
result = []
result += postorderTraversal(root.left)
result += postorderTraversal(root.right)
result.append(root.val)
return result
迭代實現:
def postorderTraversal(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)
return result[::-1]
以上是常見的三種二叉樹遍歷方式的代碼示例。根據具體需求選擇合適的遍歷方式。