1.题目要求对比总结二叉树三种遍历方式递归方式 和 非递归方式2.Python实现2.1 先序遍历题目LeetCode 144. 二叉树的前序遍历解答先输出根节点根 → 左 → 右# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# 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:nodestack.pop()res.append(node.val)# 和后序区别先右、后左入栈ifnode.right:# 特别注意的地方stack.append(node.right)ifnode.left:stack.append(node.left)returnres2.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[]currootwhilecurorstack:whilecur:# 1. 不断向左走节点全部入栈stack.append(cur)curcur.left curstack.pop()# 2. 左走到尽头弹出栈顶节点并访问res.append(cur.val)curcur.right# 3. 转向右子树继续遍历returnres2.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:nodestack.pop()res.append(node.val)ifnode.left:# 特别注意的地方stack.append(node.left)ifnode.right:stack.append(node.right)returnres[::-1]