从前序与中序遍历序列构造二叉树
一、题目描述：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
- 先根据前序序列得到当前节点的值( preorder[0] )
- 申请当前树节点, 并初始化
- 如果序列长度为1, 说明这颗树只有根节点，直接返回这个节点
- 查找中序序列里当前节点值(没有重复元素)，找得到两子树的序列长度
- 将左子树前序序列, 右子树前序序列，左子树中序序列, 右子树中序序列创建出来
- 以左子树，右子树分类，进行递归, 构造左右子树( 回到步骤1 ), 将返回结果(子树根节点)赋值给左右指针
- 返回这个节点
三、AC 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public 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;
// 严格上说还要做数组下标是否越界的判断 pivotIndex < inRight
while (inorder[pivotIndex] != pivot) {
pivotIndex++;
}
root.left = buildTree(preorder, preLeft + 1, pivotIndex - inLeft + preLeft,
inorder, inLeft, pivotIndex - 1);
root.right = buildTree(preorder, pivotIndex - inLeft + preLeft + 1, preRight,
inorder, pivotIndex + 1, inRight);
return root;
}
}
四、总结：
掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐
希望对你有帮助
期待下次再见~
🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 ~关注Jam，从你我做起！
