leetcode刷题（97）——105. 从前序与中序遍历序列构造二叉树

本文主要是介绍leetcode刷题（97）——105. 从前序与中序遍历序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

 	3/ \9  20/  \15   7

1.先回顾前序遍历和中序遍历的框架：

void traverse(TreeNode root) {// 前序遍历preorder.add(root.val);traverse(root.left);traverse(root.right);
}void traverse(TreeNode root) {traverse(root.left);// 中序遍历inorder.add(root.val);traverse(root.right);
}

在这里插入图片描述
通过上面的图观察规律，前序遍历第一个值肯定是根结点，中序遍历，根结点左边都是左子树，右边都是右子树

对于preorder数组呢？如何确定左右数组对应的起始索引和终止索引？

这个可以通过左子树的节点数推导出来，假设左子树的节点数为leftSize，那么preorder数组上的索引情况是这样的：
在这里插入图片描述

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helpBuild(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}private TreeNode helpBuild(int[] preorder,int preStart,int preEnd,int[] inorder,int inorderStart,int inordorEnd){if(preStart>preEnd){return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int index = 0;for(int i=0;i<=inordorEnd;i++){if(rootVal == inorder[i]){index = i;break;}}int leftSize = index - inorderStart;root.left = helpBuild(preorder,preStart+1,preStart+leftSize,inorder,inorderStart,index-1);root.right = helpBuild(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inordorEnd);return root;}
}