Python 树的遍历递归和循环树的遍历递归和循环
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
###递归的形式 先序遍历 中序遍历 后序遍历
def preOrderRecursive(root):
if root == None:
return None
print(root.val)
preOrderRecursive(root.left)
preOrderRecursive(root.right)
def midOrderRecursive(root):
if root == None:
return None
midOrderRecursive(root.left)
print(root.val)
midOrderRecursive(root.right)
def latOrderRecursive(root):
if root == None:
return None
latOrderRecursive(root.left)
latOrderRecursive(root.right)
print(root.val)
###循环的形式 先根遍历 中根遍历 后根遍历
###递归和循环可以互相转化
def preOrder(root):
if root == None:
return None
stack = [] tmpNode = root
while tmpNode or stack:
while tmpNode:
print(tmpNode.val)
stack.append(tmpNode)
tmpNode = tmpNode.left
node = stack.pop()
tmpNode = node.right
def midOrder(root):
if root == None:
return None
stack = [] tmpNode = root
while tmpNode or stack:
while tmpNode:
stack.append(tmpNode)
tmpNode = tmpNode.left
node = stack.pop()
print(node.val)
tmpNode = node.right
def latOrder(root):
if root == None:
return None
stack = [] tmpNode = root
while tmpNode or stack:
while tmpNode:
stack.append(tmpNode)
tmpNode = tmpNode.left
node = stack[-1] tmpNode = node.right
if node.right == None:
print(node.val)
评论0