遍历二叉树

前序遍历：

1. 先访问根节点
2. 递归遍历左子树
3. 递归遍历右子树

中序遍历

1. 递归遍历左子树
2. 访问根节点
3. 递归遍历右子树

方法一：递归

我们可以从前序遍历的中，找到根节点的值，再拿着这个根节点的值去中序遍历中找到根节点的位置
该根节点将中序遍历的数组分为左右两个部分，分别是根节点的左子树和右子树
这样我们就可以再从前序遍历中找到左子树的根节点，去遍历中序遍历的左半部分
找到右子树的根节点，去遍历中序遍历的右半部分

前序遍历：

[根节点,[左子树的前序遍历结果],[右子树的前序遍历结果]]

中序遍历：

[[左子树的前序遍历结果],根节点,[右子树的前序遍历结果]]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。这样我们就可以在前序遍历序列中找到左子树的根节点和右子树的根节点。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样一来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

函数

myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)

解释

preorder：前序遍历数组
inorder：中序遍历数组
preorder_left：在前序遍历数组中，当前要访问的树的左区间位置
preorder_right：在前序遍历数组中，当前要访问的树的右区间位置
inorder_left：在中序遍历数组中，当前要访问的树的左区间位置
inorder_right：在中序遍历数组中，当前要访问的树的左区间位置

1. 找出根节点在前序遍历数组的定位
2. 找出根节点在中序遍历数组中的定位
3. 建立根节点
4. 得到左子树的节点数目，递归地构造左子树，将根节点的左子节点指向左子树的根节点
5. 得到右子树的节点数目，递归地构造右子树，将根节点的右子节点指向右子树的根节点
6. 返回根节点

技巧：

在中序遍历中找根节点的定位时，需要花费O（n）的时间复杂度，因此将中序遍历放在一个哈希映射里，键存节点的值，值存定位。这样要找到值对应的定位，只需花费O（1）的时间复杂度

class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        //获得根节点在两个遍历中的定位
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}