【Leetcode 热题 100】105. 从前序与中序遍历序列构造二叉树

问题背景

给定两个整数数组 $preorder$ 和 $inorder$，其中 $preorder$ 是二叉树的 先序遍历， $inorder$ 是同一棵树的 中序遍历，请构造二叉树并返回其根节点。

数据约束

• $1\le preorder.length\le 3000$
• $inorder.length=preorder.length$
• $-3000\le preorder[i],inorder[i]\le 3000$
• $preorder$ 和 $inorder$ 均 无重复 元素
• $inorder$ 均出现在 $preorder$
• $preorder$ 保证 为二叉树的前序遍历序列
• $inorder$ 保证 为二叉树的中序遍历序列

解题过程

大体上的流程就是不断地从先序序列中确定根节点，再从中序序列中根据这个根节点的位置去划分左右子树，这样就能构建每一棵子树。
需要注意的是，用哈希表存储中序序列中每个节点出现的位置，能够避免在递归的过程中再用循环查找，能够提高效率。
通过这道题体会到的是，保证方法实现的正确性之后，剩下只要调用的时候填对参数就行了。

碎碎念：几年前第一次看这个实现的时候一窍不通，难过地掉头发。如今能不看题解自己想到定义哈希表，完整地实现出来，原来从不得其门而入到现在已经过去这么久了……

具体实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 能够确定长度的列表，在初始化的时候就定好，尽可能地避免扩容，养成好习惯
        Map<Integer, Integer> map = new HashMap<>(n);
        for(int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return dfs(preorder, 0, n, 0, n, map);
    }

    private TreeNode dfs(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> map) {
        if(preL == preR) {
            return null;
        }
        // 根据左子树中元素的数量来确定某几个参数，体会一下偏移的思想
        int leftCount = map.get(preorder[preL]) - inL;
        // 其中有几个参数要加一，是因为要跳过当前节点本身
        TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftCount, inL, inL + leftCount, map);
        TreeNode right = dfs(preorder, preL + 1 + leftCount, preR, inL + 1 + leftCount, inR, map);
        return new TreeNode(preorder[preL], left, right);
    }
}