1. 面试题二叉树的前序、中序、后序遍历分别是什么核心思路一句话“前、中、后”描述的是根节点访问时机前序是“根左右”中序是“左根右”后序是“左右根”。解决方案流程图遍历二叉树 │ ├── 前序根 → 左 → 右 │ ├── 中序左 → 根 → 右 │ └── 后序左 → 右 → 根结构化逻辑思维记忆时不要死记整句话只需要抓住一个核心左、右的位置基本固定 ↓ 区别只有“根”什么时候访问 ↓ 前序根在前 中序根在中 后序根在后例如A / \ B C / \ D E三种遍历结果前序A B D E C 中序D B E A C 后序D E B C A底层实现原理递归实现非常直观前序 visit(root) traverse(root.left) traverse(root.right) 中序 traverse(root.left) visit(root) traverse(root.right) 后序 traverse(root.left) traverse(root.right) visit(root)本质就是改变visit(root)的位置。完整示例代码// 二叉树节点classTreeNode{constructor(value,leftnull,rightnull){this.valuevalue;this.leftleft;this.rightright;}}// 构造一棵二叉树constrootnewTreeNode(A,newTreeNode(B,newTreeNode(D),newTreeNode(E)),newTreeNode(C));// 前序根 - 左 - 右functionpreorder(root,result[]){if(rootnull)returnresult;result.push(root.value);// 先访问根preorder(root.left,result);// 再访问左子树preorder(root.right,result);// 最后访问右子树returnresult;}// 中序左 - 根 - 右functioninorder(root,result[]){if(rootnull)returnresult;inorder(root.left,result);// 先访问左子树result.push(root.value);// 再访问根inorder(root.right,result);// 最后访问右子树returnresult;}// 后序左 - 右 - 根functionpostorder(root,result[]){if(rootnull)returnresult;postorder(root.left,result);// 先访问左子树postorder(root.right,result);// 再访问右子树result.push(root.value);// 最后访问根returnresult;}console.log(preorder(root));// [A, B, D, E, C]console.log(inorder(root));// [D, B, E, A, C]console.log(postorder(root));// [D, E, B, C, A]复杂度对于包含n个节点的二叉树时间复杂度O(n) 空间复杂度 递归调用栈O(h) h 树的高度最坏情况下二叉树退化成链表h n 空间复杂度 O(n)如果是比较平衡的树h ≈ log n 空间复杂度 O(log n)主要矛盾遍历顺序不同。次要矛盾递归还是迭代以及空间复杂度。2. 面试题二叉树的不同遍历方式分别有什么使用场景核心思路一句话不是“哪种遍历更好”而是看你需要什么顺序访问父节点优先用前序获取有序结果常用中序子节点处理完再处理父节点常用后序。解决方案架构图二叉树遍历 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 前序 中序 后序 根左右 左根右 左右根 │ │ │ ↓ ↓ ↓ 父节点优先处理 二叉搜索树排序 子节点先处理 │ │ │ ↓ ↓ ↓ 树结构复制/序列化 获取有序序列 表达式计算/ 文件目录类比 第K小元素 删除/释放等① 前序遍历根 → 左 → 右适合先处理父节点再处理子节点的场景。例如A / \ B C前序A → B → C一个典型场景是树结构的序列化、复制以及各种“先处理当前节点再处理子节点”的操作。② 中序遍历左 → 根 → 右最经典的应用是二叉搜索树Binary Search Tree的中序遍历可以得到升序排列的节点序列。例如5 / \ 3 8 / \ 1 4中序1 → 3 → 4 → 5 → 8因此可以用于二叉搜索树排序获取二叉搜索树中的第 K 小元素验证一棵树是否满足二叉搜索树的有序性注意中序遍历本身 ≠ 排序算法只有当树满足二叉搜索树的有序性质时中序遍历结果才天然有序。③ 后序遍历左 → 右 → 根核心特点处理父节点之前子节点已经处理完。因此适合存在“依赖子节点结果”的场景。例如 / \ 2 3后序2 → 3 → 这恰好对应逆波兰表达式 / 后缀表达式所以表达式计算就是一个非常典型的应用。此外后序也适合删除树计算目录总大小计算树高度计算子树信息编译器语法树处理表达式求值3. 面试题为什么二叉搜索树的中序遍历能够得到有序数组核心思路一句话因为二叉搜索树规定“左子树 根 右子树”而中序恰好按照“左 → 根 → 右”的顺序访问所以自然得到升序结果。架构图二叉搜索树性质 根 / \ 更小 更大 ↓ ↓ 左子树 右子树 ↓ 中序左 → 根 → 右 ↓ 从小到大 ↓ 有序数组示例classTreeNode{constructor(value,leftnull,rightnull){this.valuevalue;this.leftleft;this.rightright;}}constrootnewTreeNode(5,newTreeNode(3,newTreeNode(1),newTreeNode(4)),newTreeNode(8));functioninorder(root,result[]){if(rootnull)returnresult;// 先访问所有更小的节点inorder(root.left,result);// 再访问当前节点result.push(root.value);// 最后访问所有更大的节点inorder(root.right,result);returnresult;}console.log(inorder(root));// [1, 3, 4, 5, 8]边界场景需要注意普通二叉树 ↓ 中序遍历 ↓ 不一定有序只有二叉搜索树 中序遍历 ↓ 有序序列如果允许重复值还需要明确具体的二叉搜索树定义例如规定左子树 ≤ 根 右子树或者左子树 根 ≤ 右子树不同实现规则会影响重复值应该放在哪里。4. 面试题为什么表达式计算经常使用后序遍历核心思路一句话后序遍历保证一个运算符出现时它依赖的左右操作数已经准备好因此非常适合表达式求值。解决方案流程图以(2 3) * 4为例。表达式树* / \ 4 / \ 2 3后序遍历2 → 3 → → 4 → *也就是2 3 4 *这就是后缀表达式 / 逆波兰表达式。然后使用栈2 → 入栈 3 → 入栈 → 取出 2、3 → 计算 5 → 入栈 4 → 入栈 * → 取出 5、4 → 计算 20 → 入栈 最终20底层原理后序遍历最大的价值不是“顺序特殊”而是操作数 ↓ 操作数 ↓ 运算符 ↓ 可以立即计算因此可以使用栈实现。完整示例计算后缀表达式functionevaluatePostfix(expression){// 按空格拆分例如// 2 3 4 *consttokensexpression.trim().split(/\s/);conststack[];for(consttokenoftokens){// 数字直接入栈if(!Number.isNaN(Number(token))){stack.push(Number(token));continue;}// 运算符需要取出右操作数和左操作数// 注意顺序先取出来的是右操作数constrightstack.pop();constleftstack.pop();if(leftundefined||rightundefined){thrownewError(表达式不合法);}switch(token){case:stack.push(leftright);break;case-:stack.push(left-right);break;case*:stack.push(left*right);break;case/:if(right0){thrownewError(不能除以 0);}stack.push(left/right);break;default:thrownewError(不支持的运算符${token});}}// 最终应该只剩一个结果if(stack.length!1){thrownewError(表达式不合法);}returnstack[0];}console.log(evaluatePostfix(2 3 4 *));// 20如果是在线计算器怎么办不能简单地eval(userInput)因为用户输入的是不可信字符串直接执行会把它当成 JavaScript 代码。更合理的流程是用户输入 ↓ 词法分析 ↓ Token ↓ 语法分析 ↓ 抽象语法树 ↓ 后序遍历 / 直接递归求值 ↓ 计算结果如果只是实现一个简单的四则运算计算器还可以使用中缀表达式 ↓ 调度场算法 ↓ 后缀表达式 ↓ 栈求值一个简单计算器并不需要完整编译器可以实现一个词法分析器 简单语法分析器 求值器即可。5. 面试题前序、中序、后序遍历的时间复杂度和空间复杂度是多少核心思路一句话三种遍历都会访问每个节点一次所以时间复杂度都是 O(n)差别主要在访问顺序而不是时间复杂度。n 节点数量 时间复杂度 前序 O(n) 中序 O(n) 后序 O(n)递归空间O(h) h 二叉树高度例如平衡树 A / \ B C / \ D E h ≈ log n 空间 O(log n)极端退化A \ B \ C \ D h n 空间 O(n)如果改成显式栈迭代也仍然主要是时间O(n) 额外空间O(h)6. 面试题如何快速判断一道二叉树遍历题核心思路一句话先画树再只盯住“根节点什么时候输出”不要一上来死算答案。面试现场解题流程第一步画出二叉树 ↓ 第二步确认题目要求 ↓ 第三步判断“根”的位置 ↓ ┌───┼───┐ ↓ ↓ ↓ 前序 中序 后序 ↓ ↓ ↓ 根左右 左根右 左右根 ↓ 第四步从根节点递归展开 ↓ 第五步得到遍历结果记忆口诀前序根左右 中序左根右 后序左右根真正需要理解的是前、中、后只是在改变“根节点的访问时机”。满分答案面试题说一下二叉树的前序、中序、后序遍历以及它们的应用。核心思路二叉树遍历的核心区别只有一个根节点什么时候访问。前序根 → 左 → 右中序左 → 根 → 右后序左 → 右 → 根可以记成前序根左右 中序左根右 后序左右根1. 底层原理本质都是深度优先遍历只是visit(root)的位置不同前序 访问根 → 遍历左 → 遍历右 中序 遍历左 → 访问根 → 遍历右 后序 遍历左 → 遍历右 → 访问根三种遍历都会访问每个节点一次所以时间复杂度O(n) 递归空间复杂度O(h) h 是树的高度2. 主要应用前序父节点先处理。适合树结构复制、序列化以及“先处理当前节点再处理子节点”的场景。中序左 → 根 → 右。二叉搜索树满足左子树 根 右子树所以对二叉搜索树进行中序遍历可以得到升序结果也可以用于获取第 K 小元素等。后序子节点先处理。适合“必须先得到子节点结果再处理父节点”的场景例如表达式计算 树高度计算 目录大小统计 删除树节点其中表达式* / \ 4 / \ 2 3后序遍历2 → 3 → → 4 → *得到后缀表达式2 3 4 *再结合栈就可以完成求值。3. 边界和易错点第一中序遍历不等于排序只有对满足二叉搜索树性质的树进行中序遍历结果才是有序的。第二文件目录是普通多叉树不是二叉树。如果采用“先访问目录再递归访问子目录”的方式本质上属于普通树的先序深度优先遍历。第三在线计算器不应该直接使用eval(userInput)更合理的做法是用户输入 ↓ 词法分析 ↓ 语法分析 ↓ 表达式树 / 后缀表达式 ↓ 栈或树遍历求值一句话总结前序是根左右适合父节点先处理中序是左根右二叉搜索树中可以得到有序序列后序是左右根适合子节点结果先计算再处理父节点。三者时间复杂度都是 O(n)真正的区别是节点访问顺序和由此产生的应用场景。
1. 面试题二叉树的前序、中序、后序遍历分别是什么核心思路一句话“前、中、后”描述的是根节点访问时机前序是“根左右”中序是“左根右”后序是“左右根”。解决方案流程图遍历二叉树 │ ├── 前序根 → 左 → 右 │ ├── 中序左 → 根 → 右 │ └── 后序左 → 右 → 根结构化逻辑思维记忆时不要死记整句话只需要抓住一个核心左、右的位置基本固定 ↓ 区别只有“根”什么时候访问 ↓ 前序根在前 中序根在中 后序根在后例如A / \ B C / \ D E三种遍历结果前序A B D E C 中序D B E A C 后序D E B C A底层实现原理递归实现非常直观前序 visit(root) traverse(root.left) traverse(root.right) 中序 traverse(root.left) visit(root) traverse(root.right) 后序 traverse(root.left) traverse(root.right) visit(root)本质就是改变visit(root)的位置。完整示例代码// 二叉树节点classTreeNode{constructor(value,leftnull,rightnull){this.valuevalue;this.leftleft;this.rightright;}}// 构造一棵二叉树constrootnewTreeNode(A,newTreeNode(B,newTreeNode(D),newTreeNode(E)),newTreeNode(C));// 前序根 - 左 - 右functionpreorder(root,result[]){if(rootnull)returnresult;result.push(root.value);// 先访问根preorder(root.left,result);// 再访问左子树preorder(root.right,result);// 最后访问右子树returnresult;}// 中序左 - 根 - 右functioninorder(root,result[]){if(rootnull)returnresult;inorder(root.left,result);// 先访问左子树result.push(root.value);// 再访问根inorder(root.right,result);// 最后访问右子树returnresult;}// 后序左 - 右 - 根functionpostorder(root,result[]){if(rootnull)returnresult;postorder(root.left,result);// 先访问左子树postorder(root.right,result);// 再访问右子树result.push(root.value);// 最后访问根returnresult;}console.log(preorder(root));// [A, B, D, E, C]console.log(inorder(root));// [D, B, E, A, C]console.log(postorder(root));// [D, E, B, C, A]复杂度对于包含n个节点的二叉树时间复杂度O(n) 空间复杂度 递归调用栈O(h) h 树的高度最坏情况下二叉树退化成链表h n 空间复杂度 O(n)如果是比较平衡的树h ≈ log n 空间复杂度 O(log n)主要矛盾遍历顺序不同。次要矛盾递归还是迭代以及空间复杂度。2. 面试题二叉树的不同遍历方式分别有什么使用场景核心思路一句话不是“哪种遍历更好”而是看你需要什么顺序访问父节点优先用前序获取有序结果常用中序子节点处理完再处理父节点常用后序。解决方案架构图二叉树遍历 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 前序 中序 后序 根左右 左根右 左右根 │ │ │ ↓ ↓ ↓ 父节点优先处理 二叉搜索树排序 子节点先处理 │ │ │ ↓ ↓ ↓ 树结构复制/序列化 获取有序序列 表达式计算/ 文件目录类比 第K小元素 删除/释放等① 前序遍历根 → 左 → 右适合先处理父节点再处理子节点的场景。例如A / \ B C前序A → B → C一个典型场景是树结构的序列化、复制以及各种“先处理当前节点再处理子节点”的操作。② 中序遍历左 → 根 → 右最经典的应用是二叉搜索树Binary Search Tree的中序遍历可以得到升序排列的节点序列。例如5 / \ 3 8 / \ 1 4中序1 → 3 → 4 → 5 → 8因此可以用于二叉搜索树排序获取二叉搜索树中的第 K 小元素验证一棵树是否满足二叉搜索树的有序性注意中序遍历本身 ≠ 排序算法只有当树满足二叉搜索树的有序性质时中序遍历结果才天然有序。③ 后序遍历左 → 右 → 根核心特点处理父节点之前子节点已经处理完。因此适合存在“依赖子节点结果”的场景。例如 / \ 2 3后序2 → 3 → 这恰好对应逆波兰表达式 / 后缀表达式所以表达式计算就是一个非常典型的应用。此外后序也适合删除树计算目录总大小计算树高度计算子树信息编译器语法树处理表达式求值3. 面试题为什么二叉搜索树的中序遍历能够得到有序数组核心思路一句话因为二叉搜索树规定“左子树 根 右子树”而中序恰好按照“左 → 根 → 右”的顺序访问所以自然得到升序结果。架构图二叉搜索树性质 根 / \ 更小 更大 ↓ ↓ 左子树 右子树 ↓ 中序左 → 根 → 右 ↓ 从小到大 ↓ 有序数组示例classTreeNode{constructor(value,leftnull,rightnull){this.valuevalue;this.leftleft;this.rightright;}}constrootnewTreeNode(5,newTreeNode(3,newTreeNode(1),newTreeNode(4)),newTreeNode(8));functioninorder(root,result[]){if(rootnull)returnresult;// 先访问所有更小的节点inorder(root.left,result);// 再访问当前节点result.push(root.value);// 最后访问所有更大的节点inorder(root.right,result);returnresult;}console.log(inorder(root));// [1, 3, 4, 5, 8]边界场景需要注意普通二叉树 ↓ 中序遍历 ↓ 不一定有序只有二叉搜索树 中序遍历 ↓ 有序序列如果允许重复值还需要明确具体的二叉搜索树定义例如规定左子树 ≤ 根 右子树或者左子树 根 ≤ 右子树不同实现规则会影响重复值应该放在哪里。4. 面试题为什么表达式计算经常使用后序遍历核心思路一句话后序遍历保证一个运算符出现时它依赖的左右操作数已经准备好因此非常适合表达式求值。解决方案流程图以(2 3) * 4为例。表达式树* / \ 4 / \ 2 3后序遍历2 → 3 → → 4 → *也就是2 3 4 *这就是后缀表达式 / 逆波兰表达式。然后使用栈2 → 入栈 3 → 入栈 → 取出 2、3 → 计算 5 → 入栈 4 → 入栈 * → 取出 5、4 → 计算 20 → 入栈 最终20底层原理后序遍历最大的价值不是“顺序特殊”而是操作数 ↓ 操作数 ↓ 运算符 ↓ 可以立即计算因此可以使用栈实现。完整示例计算后缀表达式functionevaluatePostfix(expression){// 按空格拆分例如// 2 3 4 *consttokensexpression.trim().split(/\s/);conststack[];for(consttokenoftokens){// 数字直接入栈if(!Number.isNaN(Number(token))){stack.push(Number(token));continue;}// 运算符需要取出右操作数和左操作数// 注意顺序先取出来的是右操作数constrightstack.pop();constleftstack.pop();if(leftundefined||rightundefined){thrownewError(表达式不合法);}switch(token){case:stack.push(leftright);break;case-:stack.push(left-right);break;case*:stack.push(left*right);break;case/:if(right0){thrownewError(不能除以 0);}stack.push(left/right);break;default:thrownewError(不支持的运算符${token});}}// 最终应该只剩一个结果if(stack.length!1){thrownewError(表达式不合法);}returnstack[0];}console.log(evaluatePostfix(2 3 4 *));// 20如果是在线计算器怎么办不能简单地eval(userInput)因为用户输入的是不可信字符串直接执行会把它当成 JavaScript 代码。更合理的流程是用户输入 ↓ 词法分析 ↓ Token ↓ 语法分析 ↓ 抽象语法树 ↓ 后序遍历 / 直接递归求值 ↓ 计算结果如果只是实现一个简单的四则运算计算器还可以使用中缀表达式 ↓ 调度场算法 ↓ 后缀表达式 ↓ 栈求值一个简单计算器并不需要完整编译器可以实现一个词法分析器 简单语法分析器 求值器即可。5. 面试题前序、中序、后序遍历的时间复杂度和空间复杂度是多少核心思路一句话三种遍历都会访问每个节点一次所以时间复杂度都是 O(n)差别主要在访问顺序而不是时间复杂度。n 节点数量 时间复杂度 前序 O(n) 中序 O(n) 后序 O(n)递归空间O(h) h 二叉树高度例如平衡树 A / \ B C / \ D E h ≈ log n 空间 O(log n)极端退化A \ B \ C \ D h n 空间 O(n)如果改成显式栈迭代也仍然主要是时间O(n) 额外空间O(h)6. 面试题如何快速判断一道二叉树遍历题核心思路一句话先画树再只盯住“根节点什么时候输出”不要一上来死算答案。面试现场解题流程第一步画出二叉树 ↓ 第二步确认题目要求 ↓ 第三步判断“根”的位置 ↓ ┌───┼───┐ ↓ ↓ ↓ 前序 中序 后序 ↓ ↓ ↓ 根左右 左根右 左右根 ↓ 第四步从根节点递归展开 ↓ 第五步得到遍历结果记忆口诀前序根左右 中序左根右 后序左右根真正需要理解的是前、中、后只是在改变“根节点的访问时机”。满分答案面试题说一下二叉树的前序、中序、后序遍历以及它们的应用。核心思路二叉树遍历的核心区别只有一个根节点什么时候访问。前序根 → 左 → 右中序左 → 根 → 右后序左 → 右 → 根可以记成前序根左右 中序左根右 后序左右根1. 底层原理本质都是深度优先遍历只是visit(root)的位置不同前序 访问根 → 遍历左 → 遍历右 中序 遍历左 → 访问根 → 遍历右 后序 遍历左 → 遍历右 → 访问根三种遍历都会访问每个节点一次所以时间复杂度O(n) 递归空间复杂度O(h) h 是树的高度2. 主要应用前序父节点先处理。适合树结构复制、序列化以及“先处理当前节点再处理子节点”的场景。中序左 → 根 → 右。二叉搜索树满足左子树 根 右子树所以对二叉搜索树进行中序遍历可以得到升序结果也可以用于获取第 K 小元素等。后序子节点先处理。适合“必须先得到子节点结果再处理父节点”的场景例如表达式计算 树高度计算 目录大小统计 删除树节点其中表达式* / \ 4 / \ 2 3后序遍历2 → 3 → → 4 → *得到后缀表达式2 3 4 *再结合栈就可以完成求值。3. 边界和易错点第一中序遍历不等于排序只有对满足二叉搜索树性质的树进行中序遍历结果才是有序的。第二文件目录是普通多叉树不是二叉树。如果采用“先访问目录再递归访问子目录”的方式本质上属于普通树的先序深度优先遍历。第三在线计算器不应该直接使用eval(userInput)更合理的做法是用户输入 ↓ 词法分析 ↓ 语法分析 ↓ 表达式树 / 后缀表达式 ↓ 栈或树遍历求值一句话总结前序是根左右适合父节点先处理中序是左根右二叉搜索树中可以得到有序序列后序是左右根适合子节点结果先计算再处理父节点。三者时间复杂度都是 O(n)真正的区别是节点访问顺序和由此产生的应用场景。
