#简介
二叉树的遍历方式一般包括前序遍历、中序遍历以及后序遍历：
-
前序遍历：根结点 | 左子树 | 右子树
-
中序遍历：左子树 | 根结点 | 右子树
-
后序遍历：左子树 | 右子树 | 根结点
二叉树遍历的性质：
-
已知二叉树的前序遍历和中序遍历可以唯一重建二叉树；
-
已知二叉树的中序遍历和后序遍历可以唯一重建二叉树；
-
已知二叉树的前序遍历和后序遍历不能唯一重构二叉树。
采用递归方式来实现二叉树的重建：
- 递归停止条件：遍历结果的数组长度为0；
- 递归流程：通过找到根结点，从而将原始遍历结果数组切分为左子树和右子树的遍历结果数组，进行递归。
- 前序遍历结果数组的第一个元素为根结点；
- 后续遍历结果数组的最后一个元素为根结点；
二叉树的结点类：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
#已知前序遍历和中序遍历重建二叉树[1]
class Solution {
public TreeNode buildTree(int[] pre, int[] in) {
// 递归停止条件
if (pre.length == 0 && in.length == 0) {
return null;
}
// 首先构建根节点
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
// 找到中序遍历中的根节点位置
if (in[i] == pre[0]) {
// 根据根节点的位置找到左子树的前序遍历和中序遍历
// 递归构建根节点的左子节点
root.left = buildTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
// 根据根节点的位置找到右子树的前序遍历和中序遍历
// 递归构建根节点的右子节点
root.right = buildTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return root;
}
}
Arrays.copyOfRange(int[] arr, int start, int end)用于复制数组。其中arr为原始数组，start是复制起始位置，end是复制结束位置，注意区间是左开右闭，即[start,end)。
#已知中序遍历和后序遍历重建二叉树[2]
class Solution {
public TreeNode buildTree(int[] in, int[] post) {
if (in.length == 0 && post.length == 0) {
return null;
}
TreeNode root = new TreeNode(post[post.length - 1]);
for (int i = 0; i < in.length; i++) {
if (in[i] == post[post.length - 1]) {
root.left = buildTree(Arrays.copyOfRange(in, 0, i), Arrays.copyOfRange(post, 0, i));
root.right = buildTree(Arrays.copyOfRange(in, i + 1, in.length), Arrays.copyOfRange(post, i, post.length - 1));
break;
}
}
return root;
}
}