106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

image1

输入: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: inorder = [-1], postorder = [-1]
输出: [-1]

提示：

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

Related Topics

  • 树
  • 数组
  • 哈希表
  • 分治
  • 二叉树

题目链接: link

解答

本题的难度是 Medium.

那根据后序遍历的定义, 后序遍历的最后一个节点一定是根节点, 而根据中序遍历的定义, 一个节点的左子树的所有节点一定在这个节点的左边, 右子树的所有节点一定在这个节点的右边. 所以我们可以根据后序遍历的最后一个节点, 在中序遍历中找到这个节点, 并且确定这个节点的左右子树的节点数量. 有了这些信息, 我们就可以递归的构建二叉树了.

  • 根据后序遍历找到当前的根节点, 并且得到剩余元素得到左右子树的前序遍历
  • 根据后序遍历和当前的中序遍历

代码如下:

class Solution {
    private HashMap<Integer, Integer> hashMap = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i);
        }
        TreeNode root = createNode(null, postorder, inorder, 0, postorder.length, 0 ,postorder.length);
        return root;
    }

    private TreeNode createNode(TreeNode parent, int[] preorder, int[] inorder, 
        int startPre, int endPre, int startIn, int endIn){
            
        if(endPre-startPre==0){return null;}
        int nodeVal  = preorder[--endPre];
        int splitIndex = hashMap.get(nodeVal);
        TreeNode node = new TreeNode(nodeVal);
        node.left = createNode(node, preorder, inorder,
                startPre, startPre  + splitIndex - startIn,
                startIn, splitIndex);
        node.right = createNode(node, preorder, inorder,
                startPre  + splitIndex - startIn, endPre,
                splitIndex+1, endIn);

        return node;
    }
}

时间开销为 2ms, 击败了67.60% 的提交, 虽然代码和昨天的几乎完全一样, 但是时间开销缺有一点差异, 但是也正常, 做了另外一题，提交了两次, 两次代码完全一样, 但是时间开销不一样.