算法题：二叉树遍历总结

1.题目要求

对比总结二叉树三种遍历方式（递归方式 和 非递归方式）

2.Python实现

2.1 先序遍历

题目：LeetCode 144. 二叉树的前序遍历
解答：先输出根节点：根 → 左 → 右

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(root):ifnotroot:returnres.append(root.val)dfs(root.left)dfs(root.right)dfs(root)returnresclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:ifnotroot:return[]res,stack=[],[root]whilestack:node=stack.pop()res.append(node.val)# 和后序区别：先右、后左入栈ifnode.right:# 特别注意的地方stack.append(node.right)ifnode.left:stack.append(node.left)returnres

2.2 中序遍历

题目：LeetCode 94. 二叉树的中序遍历
解答：中间输出根节点：左 → 根 → 右

classSolution:definorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(root):ifnotroot:returndfs(root.left)res.append(root.val)dfs(root.right)dfs(root)returnresclassSolution:definorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]stack=[]cur=rootwhilecurorstack:whilecur:# 1. 不断向左走，节点全部入栈stack.append(cur)cur=cur.left cur=stack.pop()# 2. 左走到尽头，弹出栈顶节点并访问res.append(cur.val)cur=cur.right# 3. 转向右子树继续遍历returnres

2.3 后续序遍历

题目：LeetCode 145. 二叉树的后序遍历
解答：最后输出根节点：左 → 右 → 根

classSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(root):ifnotroot:returndfs(root.left)dfs(root.right)res.append(root.val)dfs(root)returnresclassSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:ifnotroot:return[]res,stack=[],[root]whilestack:node=stack.pop()res.append(node.val)ifnode.left:# 特别注意的地方stack.append(node.left)ifnode.right:stack.append(node.right)returnres[::-1]