【LeetCodehot100】T114:二叉树展开为链表 T105：从前序与中序遍历构造二叉树

T114:二叉树展开为链表

题目要求：
给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

核心思路

前序遍历顺序+指针重排

具体操作：

1. 先展开左子树
2. 再展开右子树
3. 把左子树移到右边
4. 把原右子树接到末尾

代码实现

publicvoidflatten(TreeNoderoot){if(root==null)return;// 1️⃣ 递归展开左右子树flatten(root.left);flatten(root.right);// 2️⃣ 保存原右子树TreeNoderight=root.right;// 3️⃣ 左子树移到右边root.right=root.left;root.left=null;// 4️⃣ 找右链尾节点TreeNodecur=root;while(cur.right!=null){cur=cur.right;}// 5️⃣ 接上原右子树cur.right=right;}

本题感悟

掌握前序遍历顺序+指针重排的具体流程

1. 先展开左子树
2. 再展开右子树
3. 把左子树移到右边
4. 把原右子树接到末尾

T105：从前序与中序遍历构造二叉树

题目要求：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

核心思路

前序遍历
根 → 左 → 右
作用：

确定“根节点”
中序遍历

左 → 根 → 右
作用：

划分左右子树

前序找根，中序分左右，递归构建

思路

1️⃣ 用 preorder[preL] 找到根
2️⃣ 在 inorder 中找到根的位置 index
3️⃣ 计算左子树大小 leftSize
4️⃣ 划分左右子树范围
5️⃣ 递归构建左右子树

代码实现

classSolution{Map<Integer,Integer>map=newHashMap<>();publicTreeNodebuildTree(int[]preorder,int[]inorder){// 建立中序索引for(inti=0;i<inorder.length;i++){map.put(inorder[i],i);}returnbuild(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}privateTreeNodebuild(int[]preorder,intpreL,intpreR,int[]inorder,intinL,intinR){if(preL>preR)returnnull;// 1️⃣ 根节点introotVal=preorder[preL];TreeNoderoot=newTreeNode(rootVal);// 2️⃣ 找中序位置intindex=map.get(rootVal);// 3️⃣ 左子树大小intleftSize=index-inL;// 4️⃣ 左子树root.left=build(preorder,preL+1,preL+leftSize,inorder,inL,index-1);// 5️⃣ 右子树root.right=build(preorder,preL+leftSize+1,preR,inorder,index+1,inR);returnroot;}}