一、二叉树三种遍历到底是什么假设有一棵树A / \ B C / \ / \ D E F G1. 前序遍历Preorder顺序根 → 左 → 右结果A B D E C F G代码逻辑voidpreorder(TreeNoderoot){if(rootnull)return;visit(root);preorder(root.left);preorder(root.right);}2. 中序遍历Inorder顺序左 → 根 → 右结果D B E A F C G代码voidinorder(TreeNoderoot){if(rootnull)return;inorder(root.left);visit(root);inorder(root.right);}3. 后序遍历Postorder顺序左 → 右 → 根结果D E B F G C A代码voidpostorder(TreeNoderoot){if(rootnull)return;postorder(root.left);postorder(root.right);visit(root);}二、真正重要三个遍历隐藏的性质1. 前序遍历隐藏性质保存「结构信息」根节点永远第一个出现例如树1 / \ 2 3前序1 2 3第一个1一定是根。所以前序特别适合1复制二叉树例如旧树 1 / 2按照前序1 2创建新节点。2序列化二叉树比如LeetCode 297 二叉树序列化。保存1,2,null,null,3为什么因为前序先记录根。恢复的时候先知道谁是根再恢复左右。3表达式树例如数学(ab)*c树* / \ c / \ a b前序* a b c这就是前缀表达式。2. 中序遍历隐藏性质BST天然排序这是最重要的。普通二叉树中序左 根 右没有特殊意义。但是二叉搜索树 BST5 / \ 3 8中序3 5 8天然升序。所以LeetCode 98验证BST方法中序应该严格递增。例如5 / 3中序3 5正确。如果5 \ 3中序5 3错误。LeetCode 230第K小元素直接中序第k个。因为BST中序 排序数组LeetCode 700搜索BST利用左小右大。3. 后序遍历隐藏性质处理「依赖子节点」的问题后序左 → 右 → 根特点子问题一定先完成最后处理自己。所以特别适合1删除二叉树为什么如果删除A / B不能先删A。否则B没人管理。应该先删B 再删A后序B A2计算树高度例如A / \ B C高度A高度是多少必须知道B高度 C高度才能max(B,C)1所以先左右最后根。代码height(root){leftheight(root.left);rightheight(root.right);returnmax(left,right)1;}这是后序。3判断平衡二叉树LeetCode 110。需要先知道左右高度。然后判断当前节点。后序。三、一个非常重要的规律记住前序 根先处理 中序 根在中间处理 后序 根最后处理对应遍历根的位置适合前序最前保存结构、复制、序列化中序中间BST排序后序最后计算、删除、依赖子树四、一个更深层理解递归本质其实三种遍历只差一句代码的位置。模板dfs(node){// 前序位置dfs(node.left);// 中序位置dfs(node.right);// 后序位置}三个位置进入节点 ↓ 前序 左子树回来 ↓ 中序 右子树回来 ↓ 后序画出来进入节点 | ↓ [前序位置] | 递归左子树 | ↓ [中序位置] | 递归右子树 | ↓ [后序位置]五、面试中如何选择遍历遇到树题问自己1. 我需要先知道父节点吗例如序列化、复制→ 前序2. 我需要排序关系吗例如BST第K小→ 中序3. 我需要先知道孩子的信息吗例如高度、最大路径、删除→ 后序六、刷 LeetCode 记忆表题目遍历原因94 二叉树中序遍历中序基础98 验证BST中序判断递增230 BST第K小中序第K个有序元素105 前序中序构造树前序找根106 中序后序构造树后序找根104 最大深度后序先算孩子110 平衡二叉树后序计算高度297 序列化二叉树前序保存结构最后一句话总结不要记前序 根左右 中序 左根右 后序 左右根要记前序 我先知道自己是谁 → 构造、保存结构 中序 我处在有序位置 → BST排序 后序 我要等孩子告诉我答案 → 计算、递归返回这三个性质掌握后二叉树大部分 LeetCode 题都会从「背代码」变成「推导代码」。你现在刷 98、108、230其实正好是在建立这个核心体系。