LeetCode里面的两道题：分别是根据前序遍历中序遍历求树的结构，另外一个类似的题是根据中序遍历后序遍历求树的结构。
对于这种经典的题，自然有经典的解题思路。二话不说，直接上代码，具体的解题思路，

1.树节点的定义

public class TreeNode {

    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

2.遍历树的相关代码

public class VisitTree {

    public static void preVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.data + " ");
        preVisit(root.left);
        preVisit(root.right);
    }

    public static void inVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        inVisit(root.left);
        System.out.print(root.data + " ");
        inVisit(root.right);
    }

    public static void postVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        postVisit(root.left);
        postVisit(root.right);
        System.out.print(root.data + " ");
    }
}

3.根据前序遍历中序遍历确定树的结构

/**
 * 我们先考察先序遍历序列和中序遍历序列的特点。
 * 对于先序遍历序列，根在最前面，后面部分存在一个分割点，前半部分是根的左子树，后半部分是根的右子树。
 * 对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。
 * 当我们从上向下构建树时，我们可以通过先序遍历序列知道根节点的值，但是如何知道两个序列是在哪里分割的呢？这就要依靠中序序列了。
 * 我们在中序序列中找到这个根的值，根据这个根的坐标，我们可以知道这个根左子树有多少个节点，右子树有多少个节点。
 * 然后我们根据这个将先序遍历序列分割，通过递归再次取每个部分的第一个作为根，
 * 同时为了下一次能准确的计算出左右子树各有多少节点，我们也要同时对中序遍历序列进行分割。
 *
 */
public class PreInOrder {

    public static int preStart = 0;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return helper(0, inorder.length - 1, preorder, inorder);
    }

    private static TreeNode helper(int inStart, int inEnd, int[] preorder, int[] inorder) {
        if(preStart > preorder.length || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        int inMid = 0;
        // 找到根在中序序列中的位置，从而知道先序中的分割点
        for(int i=inStart; i<=inEnd; i++) {
            if(inorder[i] == preorder[preStart]) {
                inMid = i;
            }
        }
        preStart++;
        // 例如先序序列 1(234)(567) 中2是左子树的根
        root.left = helper(inStart, inMid - 1, preorder, inorder);
        // 先序序列 1(234)(567) 中5是右子树的根
        root.right = helper(inMid + 1, inEnd, preorder, inorder);

        return root;
    }



    public static void main(String[] args) {
        int[] preorder = {1,2,4,6,7,3,5};
        int[] inorder =  {4,6,7,2,1,5,3};
        TreeNode root = buildTree(preorder, inorder);
        VisitTree.preVisit(root);
        System.out.println();
        VisitTree.inVisit(root);
        System.out.println();
        VisitTree.postVisit(root);
    }

4.根据中序遍历后序遍历确定树的结构

/**
 * 中序序列仍然是以根节点划分为左右两边，而后序序列的特点则是根在最后，然后在跟前面的那部分中，前面部分是左子树，后面的部分是右子树。
 * 所以其实我们就是把上一题给反过来了。
 * 这题我们将后序序列的指针全局化，这样我们可以先建好右子树，再建左子树，而指针只要顺序从后向前就行了。
 */
public class PostInOrder {

    public static int postEnd = 0;

    public static TreeNode buildTree(int[] postorder, int[] inorder) {
        postEnd = postorder.length - 1;
        return helper(0, inorder.length - 1, postorder, inorder);
    }

    private static TreeNode helper(int inStart, int inEnd, int[] postorder, int[] inorder) {
        if(postEnd < 0 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd--]);
        int inMid = 0;
        for(int i=inStart; i<=inEnd; i++) {
            if(inorder[i] == root.data) {
                inMid = i;
                break;
            }
        }
        root.right = helper(inMid + 1, inEnd, postorder, inorder);
        root.left = helper(inStart, inMid - 1, postorder, inorder);
        return root;
    }

    public static void main(String[] args) {
        int[] inorder =   {4,6,7,2,1,5,3};
        int[] postorder = {7,6,4,2,5,3,1};
        TreeNode root = buildTree(postorder, inorder);
        VisitTree.preVisit(root);
        System.out.println();
        VisitTree.inVisit(root);
        System.out.println();
        VisitTree.postVisit(root);
    }
}