构造二叉树（附：序列化反序列化）
1.从前序与中序遍历序列构造二叉树（105-中）
示例：中序遍历【左 | 中 | 右】；前序遍历【中 | 左 | 右】
注意:你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
思路：递归：二叉树相关的很多问题的解决思路都有分治法的思想在里面。我们复习一下分治法的思想：把原问题拆解成若干个与原问题结构相同但规模更小的子问题，待子问题解决以后，原问题就得以解决，“归并排序”和“快速排序”都是分治法思想的应用，其中“归并排序”先无脑地“分”，在“合”的时候就麻烦一些；“快速排序”开始在 partition 上花了很多时间，即在“分”上使了很多劲，然后就递归处理下去就好了，没有在“合”上再花时间。
前序遍历数组的第 1 个数（索引为 0）的数一定是二叉树的根结点，于是可以在中序遍历中找这个根结点的索引，然后把“前序遍历数组”和“中序遍历数组”分为两个部分，就分别对应二叉树的左子树和右子树，分别递归完成就可以了。
注意：分治过程中，前序和中序的左右边界索引更新。
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
}
private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
int[] inorder, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inLeft;
while (pivotIndex < inRight && inorder[pivotIndex] != pivot) {
pivotIndex++;
}
root.left = buildTree(preorder, preLeft + 1, preLeft + pivotIndex - inLeft,
inorder, inLeft, pivotIndex - 1);
root.right = buildTree(preorder, preLeft + pivotIndex - inLeft + 1, preRight,
inorder, pivotIndex + 1, inRight);
return root;
}
}
时间复杂度：O(N^2)，这里 N 是二叉树的结点个数，每调用一次递归方法创建一个结点，一共创建 N个结点，在中序遍历中找到根结点在中序遍历中的位置，是与 N 相关的，这里不计算递归方法占用的时间。
我们可以使用空间换时间，将中序遍历的值和索引放在一个hash表中，这样就可以快速找到根节点在中序遍历数组中的索引。时间复杂度O(N)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int[] preorder;
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
if (preLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
this.preorder = preorder;
this.inorderMap = new HashMap<>();
for (int i = 0; i < inLen; ++i) {
inorderMap.put(inorder[i], i);
}
return buildTree(0, preLen - 1, 0, inLen - 1);
}
private TreeNode buildTree(int preLeft, int preRight, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int pivot = preorder[preLeft];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inorderMap.get(pivot);
root.left = buildTree(preLeft + 1, preLeft + pivotIndex - inLeft,
inLeft, pivotIndex - 1);
root.right = buildTree(preLeft + pivotIndex - inLeft + 1, preRight,
pivotIndex + 1, inRight);
return root;
}
}
2.从前序与中序遍历序列构造二叉树（106-中）
基本思路：中序遍历【左 | 中 | 右】；后序遍历【左 | 右 | 中】。同理，对于后续遍历的最后一个元素一定是根节点，我们再在中序遍历中去找这个根节点。这里直接使用hash表进行优化。代码如下。
注意这里有一个技巧：先构建右子树的想法，要是先构建的是左子树还有个确定后序区间的步骤。
示例：
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
实现代码：
class Solution {
private int[] postorder;
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int postLen = postorder.length;
int inLen = inorder.length;
if (postLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
this.postorder = postorder;
this.inorderMap = new HashMap<>();
for (int i = 0; i < inLen; ++i) {
inorderMap.put(inorder[i], i);
}
return buildTree(0, inLen - 1, 0, postLen - 1);
}
private TreeNode buildTree(int inLeft, int inRight, int postLeft, int postRight) {
if (postLeft > postRight || inLeft > inRight) {
return null;
}
int pivot = postorder[postRight];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inorderMap.get(pivot);
root.left = buildTree(inLeft, pivotIndex - 1,
postLeft, postLeft + pivotIndex - inLeft - 1);
root.right = buildTree(pivotIndex + 1, inRight,
postLeft + pivotIndex - inLeft, postRight - 1);
return root;
}
}
先构建右子树，简化代码：
class Solution {
private int postIndex;
private int[] postorder;
private int[] inorder;
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
int postLen = postorder.length;
int inLen = inorder.length;
if (postLen != inLen) {
throw new RuntimeException("Incorrect input data.");
}
postIndex = postLen - 1;
inorderMap = new HashMap<>();
for (int i = 0; i < inLen; ++i) {
inorderMap.put(inorder[i], i);
}
return buildTree(0, inLen - 1);
}
private TreeNode buildTree(int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
int pivot = postorder[postIndex];
TreeNode root = new TreeNode(pivot);
int pivotIndex = inorderMap.get(pivot);
postIndex--;
root.right = buildTree(pivotIndex + 1, inRight);
root.left = buildTree(inLeft, pivotIndex - 1);
return root;
}
}
迭代法是一种非常巧妙的实现方法。迭代法的实现基于以下两点发现。
- 如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子。
- 如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子。
「反向」的意思是交换遍历左孩子和右孩子的顺序，即反向的遍历中，右孩子在左孩子之前被遍历。
这里提供官方迭代的思路和代码：
- 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（后序遍历的最后一个节点），指针指向中序遍历的最后一个节点；
- 我们依次枚举后序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向左移动 index，并将当前节点作为最后一个弹出的节点的左儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的右儿子；
- 无论是哪一种情况，我们最后都将当前的节点入栈。
最后得到的二叉树即为答案。
代码实现：
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder == null || postorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = inorder.length - 1;
for (int i = postorder.length - 2; i >= 0; i--) {
int postorderVal = postorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.right = new TreeNode(postorderVal);
stack.push(node.right);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex--;
}
node.left = new TreeNode(postorderVal);
stack.push(node.left);
}
}
return root;
}
}
3.序列化和反序列化二叉树（297-中）
题目描述：序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
示例：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
思路：二叉树结构是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化就是把结构化的数据 "打平"，其实就是在考察二叉树的遍历方式。
对于二叉树来说需要中序遍历结果与前序或后序结果结合才能构建出来，而二叉搜索树根据特性（右子树 > 根 > 左子树）只需要前序或后序遍历结果就可以构建出来。
前序遍历：根 - 左 - 右。
序列化：
-
递归第一步是对空节点的处理；
-
序列化的结果为：根节点值 + "," + 左孩子节点值（进入递归） + "," + 右孩子节点值（进入递归）；
-
递归就是不断将 "根节点" 值添加到结果中的过程。
2 （root，其中 # 代表空节点 null） / \ 1 3/ \ / \
## 4
/ \ # #
反序列化：
- 将字符串按照拼接规则拆分成nodes列表，含有空指针信息，所以只需前序序列化既可恢复（队列存储）
- 依次取出，建立头结点，递归构建左右子树
代码实现：
public class Codec {
String SP = ",";
String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SP);
return;
}
sb.append(root.val).append(SP);
serialize(root.left, sb);
serialize(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<>();
for (String s : data.split(SP)) {
nodes.add(s);
}
return deserialize(nodes);
}
private TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
String first = nodes.removeFirst();
if (first.equals(NULL)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(first));
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
}
拓展：如果是二叉搜索树的序列化和反序列化（T449），对于二叉搜索树由于节点元素大小的关系，因此一个前序排列就可以唯一确定一个结构。
- 怎么能尽可能紧凑（占用更少的内存）！
官方给出的优化方案：
-
优化1：将节点值转换为四个字节的字符串优化空间
原方法在若节点值较小时消耗的空间较小，若节点值较大则会消耗较大的空间。这是因为一个int整数（节点值）最多占用4个字节，也就是32位
-
优化2：优化1可以在不使用分隔符的情况下完成工作。
因为所有节点的值为 4 个字节，因此我们可以把编码序列 4 个字节当作一个块，将每个块转换为整数，因此可以不使用分隔符。
