Problem Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

First, we have to recall the properties of inorder and preorder traversals here. In short, we can think that the inorder traversal can be viewed as:
[{left}, root, {right}] while the preorder traversal can be viewed as:
[root, {left}, {right}]. The observation is that the preorder traversal always begins with the root element, so we can construct the root element. Now the problem is how to build the left sub-tree and right sub-tree. And this can be achieved by the inorder traversal: given the root, we can immediately get the left and right sub-tree since root splits the array into two parts.

So now we have the idea: scan preorder traversal, the first element is root, and look it up in the inorder traversal, the left part will be the left subtree and right part will be the right subtree of the root.

Note: we can also build the BT given postorder and inorder traversal following the similar logic, the only change is that the last element of the postorder traversal is the root since it can be viewed as [{left}, {right}, root]. But be warned that we CAN NOT determine uniquely a binary tree given a preorder and postorder traversal. The ambiguity comes from the fact that we cannot know the left and right subtree.

a C++ solution

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> mp;
        for(int i=0;i<inorder.size();i++) mp[inorder[i]] = i;
        TreeNode* tree = growTree(preorder, inorder, 0, preorder.size()-1, 0, mp);
        return tree;
    }
    
    TreeNode* growTree(vector<int>& preorder, vector<int>& inorder, int left, int right, int now, unordered_map<int, int>& mp){
        if(right<left) return nullptr;
        TreeNode* curr = new TreeNode(preorder[now]);
        int mid = mp[preorder[now]];
        curr->left = growTree(preorder, inorder, left, mid-1, now+1, mp);
        curr->right = growTree(preorder, inorder, mid+1, right, now+(mid-left)+1, mp);
        return curr;
    }
};
文章目录