<数据结构/算法> leetcode hot100系列. 105. 从前序与中序遍历序列构造二叉树

[LeetCode hot 100] 105. 从前序与中序遍历序列构造二叉树

题目链接

这个题的关键是理解前序遍历的序列是：【根节点，【左子树】，【右子树】】，而中序遍历的序列是【【左子树】，根节点，【右子树】】。当我们拿到一个前序遍历的序列，唯一能确定的就是第一个数一定是根节点。拿到根节点后，由于没有重复值，所以可以确定中序遍历序列中根节点的位置，从而得到中序遍历的左子树区间和右子树区间，并且得到这两个区间的长度，这样前序遍历的左子树区间和右子树区间也可以确定了。进而，左孩子节点和右孩子节点就可以确定了。

如果我们只看前序和中序的左子树的区间，就可以再得到左子树的左右孩子，以此类推，所以这是一个递归的过程，递归的参数只需要加上两个序列的起止点，来圈定当前子树的区间。

特别地，可以使用哈希表来存放每个值在中序遍历序列中的位置，这样就不用每次都用O(n)或O(logn)的时间查一遍了。

完整代码如下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> inorderMap;
    TreeNode* recur(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd){
        if(preEnd < preStart) return nullptr;
        int rootVal = preorder[preStart];
        
        int inRootPos = inorderMap[rootVal];
        int leftSize = inRootPos - inStart;
        TreeNode* left = recur(preorder, inorder, preStart + 1, preStart + leftSize, inStart, inRootPos - 1);
        TreeNode* right = recur(preorder, inorder, preStart + leftSize + 1, preEnd, inRootPos + 1, inEnd);
        TreeNode* root = new TreeNode(rootVal, left, right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++){
            inorderMap[inorder[i]] = i;
        }
        return recur(preorder, inorder, 0, inorder.size() - 1, 0, inorder.size() - 1);
    }
};