要實現TreeNode的非遞歸遍歷,可以使用迭代方法和棧數據結構。這里以二叉樹的前序遍歷、中序遍歷和后序遍歷為例進行說明。
首先定義一個簡單的TreeNode類:
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, result = [root], []
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 inorder_traversal(root):
if root is None:
return []
stack, result = [], []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
def postorder_traversal(root):
if root is None:
return []
stack, result = [root], []
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] # 反轉列表得到正確的后序遍歷順序
這樣就實現了二叉樹的非遞歸遍歷。注意這里的遍歷順序與遞歸遍歷相同,只是實現方式不同。