105. Construct Binary Tree from Preorder and Inorder Traversal
从中序遍历和前向遍历得到一个
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
解析
查找在inorder 中根节点的index, 然后求出 左边子树的长度 为 int leftsize = index - s2
六个位置关系
preorder[ ] = [ s1, s1+1 , s1+leftsize, s1+leftsize+1, l1 ];
inorder[ ] = [s2, index-1, index, index+1 , s2]
**总结如下情况:三个位置:
- 递归结束的位置情况
- 获取根节点的位置index,
- 计算左边子树的长度 得到这几种情况的位置信息
**
/**
* 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) {
TreeNode root=null;
int n = preorder.length;
if(n==0) {return root;}
return helper(preorder,0,n-1,inorder, 0,n-1);
}
private TreeNode helper(int [] preorder, int start_1,int last_1, int []inorder, int start_2,int last_2){
//递归截止条件
if(start_1>last_1 || start_2>last_2) {return null;}
TreeNode root = new TreeNode(preorder[start_1]);
//找到的是索引位置,不是左边的元素长度情况
int index = find(preorder[start_1],inorder, start_2,last_2);
//左边的元素个数是index,
int leftsize = index-start_2;
//
// inorder : 开始位置 start_2 ,截止位置是index-1;
root.left = helper(preorder,start_1+1,start_1+leftsize,inorder, start_2,index-1);
//index + 1 代表开始位置, last_2 代表截止位置
root.right = helper(preorder,start_1+leftsize+1,last_1,inorder,index+1,last_2);
return root;
}
private int find(int element,int [] array, int start, int last){
//查找成功返回一个数组下标元素
for(int i=start;i<=last;i++){
if(array[i]==element)
{return i;}
}
//否则返回0
return -1;
}
}