题目105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
1,
分析,盗用一图, 一图胜千言
1.jpg
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
return createTree(preorder,0,inorder,0,inorder.length-1);
}
private TreeNode createTree(int[] preorder ,int preIdx, int[] inorder, int inStartIdx, int inEndIdx){
if(preIdx >= preorder.length){
return null;
}
if(inStartIdx > inEndIdx){
return null;
}
int rootVal = preorder[preIdx];
TreeNode root = new TreeNode(rootVal);
int rootIdxIn;
for(rootIdxIn=inStartIdx; rootIdxIn<=inEndIdx; rootIdxIn++){
if(rootVal == inorder[rootIdxIn]){
break;
}
}
root.left = createTree(preorder,preIdx+1,inorder,inStartIdx,rootIdxIn-1);
root.right = createTree(preorder,preIdx+(rootIdxIn-inStartIdx+1),inorder,rootIdxIn+1,inEndIdx);
return root;
}
}
