?LeetCode刷題實(shí)戰(zhàn)105：從前序與中序遍歷序列構(gòu)造二叉樹(shù)

class?Solution?{
????public?TreeNode buildTree(int[] preorder, int[] inorder) {
??????????if(preorder.length>0) {
?????????????TreeNode root =new?TreeNode(preorder[0]);
?????????????List order=new?ArrayList();
?????????????for(int?i=0;i?????????????????order.add(inorder[i]);
?????????????}
?????????????getTree(preorder,0,order,root); 
?????????????return?root;
?????????} else?{
?????????????return?null;
?????????}
????}
????
????public?void?getTree(int[]preorder ,int?number,List order,TreeNode root) {
????????if(order.size()==1) {
????????????return?;
????????}
????????
????????int?ordernum=order.indexOf(preorder[number]);
????????if(ordernum>0) {
????????List leftOrder=new?ArrayList(order.subList(0, ordernum)); 
????????for(int?i=number+1;i????????{
????????????if(leftOrder.contains(preorder[i])) {
????????????????root.left=new?TreeNode(preorder[i]);
????????????????getTree(preorder,i,leftOrder,root.left);
????????????????break;
????????????}
????????????
?????????}
????????}
????????
????????if(ordernum-1)
????????{
????????????List rightOrder=new?ArrayList(order.subList(ordernum+1, order.size()));
????????????for(int?j=number+1;j????????????????if(rightOrder.contains(preorder[j])) {
????????????????????root.right=new?TreeNode(preorder[j]);
????????????????????getTree(preorder,j,rightOrder,root.right);
????????????????????break;
????????????????}
????????????}
????????}
???????
????}
}