LeetCode.105.Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树

题目描述

105 Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

解题过程

前序遍历序列是 根, 左子树, 右子树
中序遍历序列是 左子树, 根, 右子树
所以，前序序列的第一个元素肯定是整个树的根节点，然后找到根节点在中序序列中的下标，把中序序列分为左子树和右子树，然后分别递归的进行处理。
这里有几个问题：
1、如何快速找到根节点在中序序列中的下标？
题中给出所有元素值都是唯一的，所以可以把中序序列的元素值到下标的映射关系先存入Map中，然后每次直接O(1)就能找到元素值在中序序列的下标。

2、找到根节点在中序序列里的下标后，中序序列是很容的就分为左子树序列和右子树序列了，那前序序列怎么分割呢？
我们知道，左子树的结点个数在前序和中序序列中肯定是相同的，中序序列分割后，很容易知道左子树序列的长度，所以根据这个长度值就可以很方便的对前序序列进行分割。假如当前递归的中序序列是 inorder[inStart…inEnd], 找到根节点在中序序列的下标 inOrderRootIndex 后，inOrderRootIndex - inStart 就是左子树序列的长度，知道这个长度后，就很容易分割前序序列了。

时间复杂度 O(n)，空间复杂度O(n)

private static class SolutionV202005 {
    Map<Integer, Integer> inOrderMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (null == preorder || preorder.length < 1) {
            return null;
        }
        // 中序序列的 元素 -> 下标 之间的映射，方便直接找到根节点在中序序列里的位置(前提是元素唯一)
        inOrderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    // 根据前序序列 preorder[preStart...preEnd] 和 中序序列 inorder[inStart...inEnd] 递归的构建二叉树，返回根节点
    private TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        TreeNode root = new TreeNode(preorder[preStart]); // 当前子树的根
        int inOrderRootIndex = inOrderMap.get(preorder[preStart]); // 根在中序序列中的下标
        if (inOrderRootIndex == inStart) { // 无左子树
            root.left = null;
        } else {
            root.left = buildTree(preorder, inorder, preStart+1, preStart + inOrderRootIndex - inStart, inStart, inOrderRootIndex-1);
        }
        if (inOrderRootIndex == inEnd) { // 无右子树
            root.right = null;
        } else {
            root.right = buildTree(preorder, inorder, preStart + inOrderRootIndex - inStart + 1, preEnd, inOrderRootIndex+1, inEnd);
        }
        return root;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_105_ConstructBinaryTreeFromPreorderInorder.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_105_ConstructBinaryTreeFromPreorderInorder.java

---