首页 > 代码库 > [leetcode] Construct Binary Tree from Preorder and Inorder Traversal

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

 

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public TreeNode buildTree(int[] preorder, int[] inorder) {         int len=preorder.length;         if(len==0)              return null;                      TreeNode root=new TreeNode(preorder[0]);         if(len==1)             return root;                     int index=0;         for(int i=0;i<inorder.length;i++){             if(inorder[i]==preorder[0]){                 index=i;                 break;             }         }         if(index>0){              int []preleft=new int[index];              int []inleft=new int[index];              System.arraycopy(preorder,1,preleft,0,index);              System.arraycopy(inorder,0,inleft,0,index);              root.left=buildTree(preleft,inleft);         }         if(len-index-1>0){              int []preright=new int [len-index-1];              System.arraycopy(preorder,index+1,preright,0,len-index-1);                int []inright=new int [len-index-1];              System.arraycopy(inorder,index+1,inright,0,len-index-1);                root.right=buildTree(preright,inright);         }                 return root;    }}

 

[leetcode] Construct Binary Tree from Preorder and Inorder Traversal