题解 | #从中序与后序遍历序列构造二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param postorder int整型vector 后序遍历序列
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        int size = inorder.size();
        //建立一个哈希表，来映射结点值与中序遍历数组的下标，方便查找
        unordered_map<int, int> inorder_map;
        for(int i = 0;i < size;++i)
        {
            inorder_map[inorder[i]] = i;//各节点值不相同
        }

        return buildTreeHelper(inorder, postorder, 0, size-1, 0, size-1, inorder_map);
    }

    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int in_start, int in_end, int post_start, int post_end, unordered_map<int, int> inorder_map)
    {
        if(in_start > in_end || post_start > post_end)
        {
            return nullptr;
        }
        int root_val = postorder[post_end];//后序遍历：左右根
        auto root = new TreeNode(root_val);//新建根节点
        int root_index = inorder_map[root_val];//通过哈希表，找到根节点下标
        int left_size = root_index - in_start;//左子树的大小
        root->left = buildTreeHelper(inorder, postorder, in_start, root_index-1, post_start, post_start+left_size-1, inorder_map);
        root->right = buildTreeHelper(inorder, postorder, root_index+1, in_end, post_start+left_size, post_end-1, inorder_map);

        return root;
    }
};