leetcode-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.

For example, given

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

Return the following binary tree:

3 / \ 9 20 / \ 15 7

 

 

/**  * 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) {         if(preorder== null || inorder == null || preorder.length == 0) {             return null;         }else if(preorder.length != inorder.length){             return null;         }                  return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);                  }          public TreeNode buildTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {         if(ps> pe || is>ie) {             return null;         }         TreeNode begin = new TreeNode(preorder[ps]);         if(ps == pe && is== ie) {             return begin;         }                  //找到再中序中对应的位置，划分为左右树节点                  int tmpIe = -1;         for(int index=is;index<=ie;index++) {             if(inorder[index] == preorder[ps]) {                 tmpIe = index;                 break;             }         }                               //找到前序中，在中序中左节点的结束位置         int tmpPe = ps+tmpIe-is+1;         begin.left = buildTree(preorder,ps+1,tmpPe-1,inorder,is,tmpIe-1);         begin.right = buildTree(preorder,tmpPe,pe,inorder,tmpIe+1,ie);         return begin;     } }