华为员工偷偷跑出去面试，被面试官鄙视了。第一句话就问：35岁了，身体没啥毛病吧？

(关注数据结构和算法，了解更多新知识)

最近一网友发文说自己偷偷跑出去面试，直接被鄙视了，对方说：华为淘汰的吧，35岁了，这个年龄在华为混的下去吗，身体没毛病吧。

看完之后我只能说这hr太不专业了，如果不想要35岁的完全可以不要让别人来面试啊。简历上一般都会有身份证号，有的还会有年龄，看到简历就应该知道别人的年龄，既然不要年龄大的，为啥还要让别人白跑一趟，这hr妥妥的250。

我想起前几年有次我面试的时候，都二面了，结果面完之后面试官突然来一句：我们不需要这么长工作经验的。听完之后我真的想搂脸呼他一巴掌，不需要那么长工作经验为啥还和我聊那么久。

对于这件事我倒不是关注35岁的问题，我关注的是明明知道别人不合适，不会录用别人，为啥还要别人过来面试，我现在特别好奇hr找人面试是不是有指标的，是不是也要作为绩效考核的一部分。最后我们再来看下各位网友的评论：

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第106题：从中序与后序遍历序列构造二叉树。

问题描述

来源：LeetCode第106题
难度：中等
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树 。

示例1：

输入：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 保证是树的后序遍历

问题分析

这题是让根据中序和后续遍历数组来还原二叉树，我们知道二叉树后序数组的最后一个元素一定是根节点，因为后序遍历的顺序是先遍历左右子树在遍历根节点。而中序遍历是根节点的左子树都遍历完了才遍历根节点，所以在中序数组中，根节点前面的元素是他的左子树节点，后面的元素是他右子树的节点。

根据这个特性我们可以把中序数组和后序数组划分两部分，然后每部分继续按照上面的方法划分，直到只有一个节点，不能划分为止。比如示例 1 的数组划分如下图所示。

划分的时候我们没必要把数组进行截取，只需要使用几个变量分别记录下后序和中序数组的区间范围即可。因为我们是根据后序数组中的元素在中序数组中的位置来划分中序数组的，所以这里只需要记录中序数组的范围，后序数组只需要记录起始位置即可。

JAVA：

public TreeNode buildTree(int[] inorder, int[] postorder) {
    // 为了方便后续进行查找，先把中序数组的所有值存储到map中
    Map<Integer, Integer> map = new HashMap<>();
    int length = inorder.length;
    for (int i = 0; i < length; i++)
        map.put(inorder[i], i);
    return build(postorder, map, length - 1, 0, length - 1);
}

private TreeNode build(int[] postorder, Map<Integer, Integer> map,
                       int postEnd, int inStart, int inEnd) {
    if (inStart > inEnd) return null;// 表示数组被访问完了。
    // 使用后序数组的最后一个元素创建根节点
    TreeNode root = new TreeNode(postorder[postEnd]);
    // 查找根节点在中序数组中位置
    int index = map.get(root.val);
    int rightCount = inEnd - index;// 右子树的所有节点个数
    // 后序数组区间划分：
    // [……, postEnd-rightCount-1]左子树
    // [postEnd-rightCount, postEnd-1]右子树
    // [postEnd, postEnd]根节点
    // 中序数组区间划分：
    // [inStart, index - 1]左子树
    // [index, index]根节点
    // [index + 1, inEnd]右子树
    root.left = build(postorder, map, postEnd - rightCount - 1, inStart, index - 1);
    root.right = build(postorder, map, postEnd - 1, index + 1, inEnd);
    return root;
}

C++：

public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // 为了方便后续进行查找，先把中序数组的所有值存储到map中
        unordered_map<int, int> m;
        int length = inorder.size();
        for (int i = 0; i < length; i++)
            m[inorder[i]] = i;
        return build(postorder, m, length - 1, 0, length - 1);
    }

    TreeNode *build(vector<int> &postorder, unordered_map<int, int> &m,
                    int postEnd, int inStart, int inEnd) {
        if (inStart > inEnd)
            return nullptr;// 表示数组被访问完了。
        // 使用后序数组的第一个元素创建根节点
        TreeNode *root = new TreeNode(postorder[postEnd]);
        // 使用后序数组的最后一个元素创建根节点
        int index = m[root->val];
        int rightCount = inEnd - index;// 右子树的所有节点个数
        // 后序数组区间划分：
        // [……, postEnd-rightCount-1]左子树
        // [postEnd-rightCount, postEnd-1]右子树
        // [postEnd, postEnd]根节点
        // 中序数组区间划分：
        // [inStart, index - 1]左子树
        // [index, index]根节点
        // [index + 1, inEnd]右子树
        root->left = build(postorder, m, postEnd - rightCount - 1, inStart, index - 1);
        root->right = build(postorder, m, postEnd - 1, index + 1, inEnd);
        return root;
    }

C：

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} hashTable;

hashTable *hashtable = NULL;

hashTable *find(int ikey) {
    hashTable *pEntry;
    HASH_FIND_INT(hashtable, &ikey, pEntry);
    return pEntry;
}

void insert(int ikey, int ival) {
    hashTable *pEntry = malloc(sizeof(hashTable));
    pEntry->key = ikey, pEntry->val = ival;
    HASH_ADD_INT(hashtable, key, pEntry);
}

void hashFree() {
    hashTable *cur = NULL, *tmp = NULL;
    HASH_ITER(hh, hashtable, cur, tmp) {
        HASH_DEL(hashtable, cur);
        free(cur);
    }
}

struct TreeNode *build(int *postorder, int postEnd, int inStart, int inEnd) {
    if (inStart > inEnd)
        return NULL;// 表示数组被访问完了。
    // 使用后序数组的第一个元素创建根节点
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = postorder[postEnd];
    // 查找根节点在中序数组中位置
    int index = find(root->val)->val;
    int rightCount = inEnd - index;// 右子树的所有节点个数
    // 后序数组区间划分：
    // [……, postEnd-rightCount-1]左子树
    // [postEnd-rightCount, postEnd-1]右子树
    // [postEnd, postEnd]根节点
    // 中序数组区间划分：
    // [inStart, index - 1]左子树
    // [index, index]根节点
    // [index + 1, inEnd]右子树
    root->left = build(postorder, postEnd - rightCount - 1, inStart, index - 1);
    root->right = build(postorder, postEnd - 1, index + 1, inEnd);
    return root;
}

struct TreeNode *buildTree(int *inorder, int inorderSize, int *postorder, int postorderSize) {
    // 为了方便后续进行查找，先把中序数组的所有值存储到map中
    for (int i = 0; i < postorderSize; i++)
        insert(inorder[i], i);
    struct TreeNode *ans = build(postorder, postorderSize - 1, 0, postorderSize - 1);
    hashFree();// 释放内存，否则会出现内存溢出
    return ans;
}

Python：

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    def build(postEnd: int, inStart: int, inEnd: int):
        if inStart > inEnd:
            return None  # 表示数组被访问完了。
        # 使用后序数组的最后一个元素创建根节点
        root = TreeNode(postorder[postEnd])
        # 查找根节点在中序数组中位置
        index = m[root.val]
        rightCount = inEnd - index  # 右子树的所有节点个数
        '''
        后序数组区间划分：
        [……, postEnd-rightCount-1]左子树
        [postEnd-rightCount, postEnd-1]右子树
        [postEnd, postEnd]根节点

        中序数组区间划分：
        [inStart, index - 1]左子树
        [index, index]根节点
        [index + 1, inEnd]右子树
        '''
        root.left = build(postEnd - rightCount - 1, inStart, index - 1)
        root.right = build(postEnd - 1, index + 1, inEnd)
        return root

    # 为了方便后续进行查找，先把中序数组的所有值存储到map中
    m = {element: i for i, element in enumerate(inorder)}
    return build(len(postorder) - 1, 0, len(postorder) - 1)

笔者简介

博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。