当前位置 博文首页 > dastu的博客：二叉树的前中后序遍历 递归/非递归（python版）
中序遍历（非递归）：
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[]
if not root:
return root
while root or stack:
while root:
stack.append(root)
root=root.left
if stack:
temp=stack.pop()
res.append(temp.val)
root=temp.right
return res
中序遍历（递归）：
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
if not root:
return res
left=self.postorderTraversal(root.left)
right=self.postorderTraversal(root.right)
res.extend(left)
res.append(root.val)
res.extend(right)
return res
后序遍历（非递归）
def postorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
result = []
tag = None
if not root:
return result
while stack or root:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
if cur.right == None or cur.right == tag:
result.append(cur.val)
tag = cur
root=None
else:
print(cur.val,result)
stack.append(cur)
root = cur.right
return result
后序遍历（递归）：
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
if not root:
return res
left=self.postorderTraversal(root.left)
right=self.postorderTraversal(root.right)
res.extend(left)
res.extend(right)
res.append(root.val)
return res
先序遍历（非递归）
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
stack=[]
if not root:
return []
while root or stack:
while root:
stack.append(root)
res.append(root.val)
root=root.left
if stack:
cur=stack.pop()
root=cur.right
return res
先序遍历（递归）
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return None
result=[]
result.append(root.val)
left=self.preorderTraversal(root.left)
right=self.preorderTraversal(root.right)
result.extend(left)
result.extend(right)
return result
对应Leetcode144题（前序) 94题（中序）145题（后序）
cs