目录一、二叉树展开为链表前序遍历秒杀 题目要求 超简单思路✅ 完整解题代码 小白通俗解析二、从前序与中序遍历序列构造二叉树递归分治经典 题目要求 核心思路小白秒懂✅ 完整解题代码 小白通俗解析 两道题终极口诀秒记二叉树展开为链表前序 中序还原二叉树 总结一、二叉树展开为链表前序遍历秒杀 题目要求给定一个二叉树将它展开成一个 **“单链表”**要求展开后的链表使用原树节点所有节点的左孩子为 null右孩子指向下一个节点顺序与前序遍历一致 超简单思路前序遍历二叉树把所有节点按顺序存到集合里遍历集合把前一个节点的左孩子置空右孩子指向后一个节点链表拼接完成✅ 完整解题代码java运行/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { // 存储前序遍历的所有节点 private ListTreeNode list new ArrayList(); public void flatten(TreeNode root) { if(root null) return; // 1. 前序遍历收集所有节点 travle(root); // 2. 拼接成单向链表 for(int i 0; i list.size() - 1; i){ TreeNode pre list.get(i); TreeNode cur list.get(i1); // 左孩子置空 pre.left null; // 右孩子指向下一个节点 pre.right cur; } } // 前序遍历根 → 左 → 右 public void travle(TreeNode node) { if(node null) return; // 先收集当前节点 list.add(node); // 遍历左子树 travle(node.left); // 遍历右子树 travle(node.right); } } 小白通俗解析前序遍历 根节点先加入再遍历左右子树用集合保存所有节点后直接按顺序拼接左边全部清空右边连成一条线就是题目要求的链表代码短短几行逻辑一目了然面试写这个最快最稳二、从前序与中序遍历序列构造二叉树递归分治经典 题目要求给定二叉树的前序遍历和中序遍历数组还原出这棵二叉树。 核心思路小白秒懂前序遍历第一个节点 整棵树的根节点在中序遍历中找到根节点位置根节点左边 左子树根节点右边 右子树用递归分治不断切割数组重复找根→建节点→分左右子树用 Map 记录中序遍历值与下标快速找根节点位置✅ 完整解题代码java运行/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { // 记录中序数组值 → 下标快速定位根节点 private MapInteger, Integer map new HashMap(); public TreeNode buildTree(int[] preorder, int[] inorder) { // 把中序数组存入map for(int i 0; i inorder.length; i){ map.put(inorder[i], i); } // 递归建树左闭右开区间 return find(preorder, 0, preorder.length, inorder, 0, inorder.length); } // 递归分治建树 public TreeNode find(int[] preorder, int preorderBegin, int preorderEnd, int[] inorder, int inorderBegin, int inorderEnd){ // 递归终止条件区间无效 if(preorderBegin preorderEnd || inorderBegin inorderEnd){ return null; } // 前序第一个节点 根节点 int rootVal preorder[preorderBegin]; // 找到根节点在中序数组中的位置 int rootIndex map.get(rootVal); TreeNode root new TreeNode(rootVal); // 左子树节点个数 int leftSize rootIndex - inorderBegin; // 递归构建左子树 root.left find(preorder, preorderBegin 1, preorderBegin 1 leftSize, inorder, inorderBegin, rootIndex); // 递归构建右子树 root.right find(preorder, preorderBegin 1 leftSize, preorderEnd, inorder, rootIndex 1, inorderEnd); return root; } } 小白通俗解析前序找根中序分左右用 Map 快速定位根节点避免每次遍历数组按区间切割数组递归建左右子树标准分治递归思想代码规范面试必背模板 两道题终极口诀秒记二叉树展开为链表前序遍历存节点循环拼接右指针左边全部置为空前序 中序还原二叉树前序找根中序分左右递归切割分治建树 总结这两道题是二叉树最经典、最高频的面试题一道考察前序遍历 链表拼接一道考察递归分治 还原二叉树都是刷题必掌握核心知识点。代码简洁、思路清晰学会这两道二叉树递归 / 遍历题型直接通关