一、链表

public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
    }
}

二、二叉树

public class TreeNode {
    int val;
    TreeNode leftNode;
    TreeNode rightNode;
    TreeNode(int x) {
        val = x;
    }
}

• 前序遍历-先输出当前结点的数据，再依次遍历输出左结点和右结点
• 中序遍历-先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点
• 后序遍历- 先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据
• 已知前序遍历和后序遍历，无法确定一颗唯一的二叉树

//已知前序和中序
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0) {
        return null;
    }
    Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
    int length = preorder.length;
    for (int i = 0; i < length; i++) {
        indexMap.put(inorder[i], i);
    }
    TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
    return root;
}

public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
    if (preorderStart > preorderEnd) {
        return null;
    }
    int rootVal = preorder[preorderStart];
    TreeNode root = new TreeNode(rootVal);
    if (preorderStart != preorderEnd) {
        //获取根节点在中序遍历的index
        int rootIndex = indexMap.get(rootVal);
        //获取根节点左右的开始index
        int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
        TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
        TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
        root.left = leftSubtree;
        root.right = rightSubtree;
    }
    return root;
}