Leetcode 从前序与中序遍历序列构造二叉树

inorderStart 和 inorderEnd 是中序遍历序列下标索引。

java 递归实现

class Solution {
    private HashMap<Integer, Integer> inorderIndexMap;
    private int preorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();
        preorderIndex = 0;

        for(int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i); //存放中序遍历值和索引的映射
        }

        return Helper(preorder, 0, inorder.length - 1);
        
    }

    private TreeNode Helper(int[] preorder, int inorderStart, int inorderEnd) {
        if(inorderStart > inorderEnd) return null;

        //首先从先根遍历序列中获取当前节点值
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);

        //在中根遍历中找到根节点的位置
        int inorderIndex = inorderIndexMap.get(rootValue);

        //构建左子树
        root.left = Helper(preorder, inorderStart, inorderIndex - 1);

        //构建右子树
        root.right = Helper(preorder, inorderIndex + 1, inorderEnd);

        return root;
    }
}