<Data Structures/Algorithms> leetcode hot100 - 105. Construct Binary Tree from Preorder and Inorder Traversal

[LeetCode Hot 100] 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Link

The key to this problem is understanding that:

• Preorder traversal sequence is: [root, left subtree, right subtree]
• Inorder traversal sequence is: [left subtree, root, right subtree]

Given a preorder sequence, the first element is always the root. Once we know the root, and since all values are unique, we can find the root’s position in the inorder sequence. This allows us to determine the ranges of the left and right subtrees in the inorder sequence and calculate their lengths, which in turn gives the ranges for the preorder left and right subtrees. This way, the left and right child nodes can be determined.

Recursively, we can do the same for each subtree by narrowing the ranges. The recursion parameters are simply the start and end indices for the preorder and inorder sequences to define the current subtree range.

Additionally, a hash map can store the index of each value in the inorder sequence for O(1) lookup, avoiding repeated O(n) searches.

/**
 * 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);
    }
};

中文原文

[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);
    }
};