題目:?已知二叉樹的前序序列和中序序列求解樹
比如
6
4 8
3 5 ?7
前序序列為6,4,3,5,8,7
中序序列為3,4,5,6,7,8
思路: 前序遍歷序列的第一個元素必為根節點 則中序遍歷序列中，該節點之前的為左子樹，該節點之后的為右子樹，若該節點之前沒有節點，則左子樹為空，反之右子樹為空，
截取個子樹的前序和中序序列，重復上述邏輯遞歸求解
?
我自己的思路是只根據前序遍歷序列也可得到：同理前序第一個元素為根節點，向后依次比較后續元素，直到找到第一個比根元素大的，則該元素與根元素之間的所有元素（不包括）為左子樹，該元素之后的所有元素（包括）為右子樹，對子樹使用相同邏輯遞歸即可，但需要判斷子樹為空的情況?
?
1 package com.rui.microsoft; 2 3 import java.util.Arrays; 4 5 public class Tree_BuildTreeByPreMid { 6 7 public static void main(String[] args) { 8 9 int[] pre = {6,4,3,5,8,7}; 10 //int[] mid = {3,4,5,6,7,8}; 11 12 Node root = Tree_BuildTreeByPreMid.build(pre); 13 System.out.println(root.value); 14 } 15 16 public static Node build(int[] pre){ 17 int rootV = pre[0]; 18 Node root = new Node(rootV); 19 20 int left = 1; 21 while(left < pre.length && pre[left] < rootV) left++; 22 23 //No left tree, because the pointer left has not changed 24 if(left == 1){ 25 root.left = null; 26 }else{ 27 int[] leftArray = Arrays.copyOfRange(pre, 1, left); 28 root.left = build(leftArray); 29 } 30 31 //No right tree, because the pointer left has been moved to the end of the array 32 if(left == pre.length){ 33 root.right = null; 34 }else{ 35 int[] rightArray = Arrays.copyOfRange(pre, left, pre.length); 36 root.right = build(rightArray); 37 } 38 39 return root; 40 } 41 42 static class Node { 43 int value; 44 Node left; 45 Node right; 46 public Node(int v){ 47 this.value = v; 48 } 49 } 50 }
?
