力扣105——从前序与中序遍历序列构造二叉树

健程之道

发布于 2020-02-02 17:25:41

4850

发布于 2020-02-02 17:25:41

文章被收录于专栏：健程之道

原题

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

原题url：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解题

这道题目，主要就是在于大家对于二叉树这个数据结构的熟悉程度了，根据其前序遍历和中序遍历，推算出原本的二叉树。

我们想想，如果不是写代码，只是通过手写的话，我们是如何查找的，就用题目给出的例子：

根据前序遍历，第一个一定是根节点，那么 3 就是根节点。
从中序遍历中寻找 3，在它左边的，都是其左子树上的节点，在它右边的，都是其右子树上的节点。
因为中序遍历中，3 的左边只有9，那么 9 就是 3 的左子节点。
根据前序遍历先根然后左子节点，然后再右子节点的规律，3 、9 之后的 20 一定是 3 的右子节点。
20 在中序遍历中，其左右两边就是 15 和 7，因此15 和 7 就分别是它的左右子节点。

根据上面的分析，你就可以画出例子中的二叉树了。

那么我们寻找的顺序是，先从前序遍历的第一个节点开始，在中序遍历中找出它的位置，其左右两边就是其左右子树了，

接着从左子树入手，前序遍历根节点之后的两个节点应该就是其左右子树，但需要考虑没有左右子树的情况，然后再以其子树为根，在中序遍历中找其左右子树。

需要注意的是，只有针对根节点，其左右子节点是在前序遍历中紧跟着根节点的，其他都是有距离的，需要根据左子树递推。

接下来看看代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;
    int[] inorder;
    // preorder中遍历过的数量，这样找完左子树中的节点，剩下的第一个节点，必然是右子节点
    int preorderIndex = 0;
    // key为inorder中的值，value为inorder中的下标
    Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }

        TreeNode node = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            return node;
        }

        this.preorder = preorder;
        this.inorder = inorder;
        this.inorderMap = new HashMap<>(inorder.length * 4 / 3 + 1);
        for (int i = 0; i < inorder.length; i++) {
            this.inorderMap.put(inorder[i], i);
        }

        return generateNode(0, inorder.length);
    }

    /**
     * 寻找当前节点的左右子节点
     * start：inorder里开始寻找的节点下标
     * end：inorder里终止寻找的节点下标
     * preorderIndex：当前节点在preorder中的下标
     */
    public TreeNode generateNode(int start, int end) {
        if (start >= end) {
            return null;
        }

        // 当前节点
        int value = preorder[preorderIndex];
        TreeNode node = new TreeNode(value);
        // 当前节点的值，在inorder中的下标
        int inorderIndex = inorderMap.get(value);

        // 当前节点已经找到，寻找下一个节点。
        // 因为会先去寻找左节点，当该节点左子树中所有节点全部找完后，前序遍历中，剩下节点的第一个节点，一定是该节点的右节点。
        preorderIndex++;

        // 寻找左节点
        node.left = generateNode(start, inorderIndex);
        // 寻找右节点
        node.right = generateNode(inorderIndex + 1, end);

        return node;
    }
}

提交OK，执行用时：3 ms，内存消耗：40.1 MB。