python二叉树遍历代码怎么写
在Python中,可以使用递归或者迭代的方式来实现二叉树的遍历。以下是常见的三种二叉树遍历方式的代码示例:
- 前序遍历(Preorder Traversal):根节点 -> 左子树 -> 右子树
递归实现:
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
- 中序遍历(Inorder Traversal):左子树 -> 根节点 -> 右子树
递归实现:
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
- 后序遍历(Postorder Traversal):左子树 -> 右子树 -> 根节点
递归实现:
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]
以上是常见的三种二叉树遍历方式的代码示例。根据具体需求选择合适的遍历方式。
相关问答