Leetcode Study Day 34

Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Solution

Firstly, we should know that the first element in preorder list is the root of the tree. Then we can find the index of the root in inorder list. Then we can split the inorder array into left and right subtrees. The next element in preorder list will be the left child, so skip the root and split the preorder array accordingly. Recursively construct the left and right subtrees.

/**
 * 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:
    int findIndex(vector<int>& array, int value){
        for (int i = 0; i < array.size(); i++){
            if( array[i] == value)
                return i;
        }
        return -1;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (empty(preorder))
            return nullptr;
        // The first element in preorder list is the root of the tree
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);

        // Find the index of the root in inorder list
        int rootIndexInOrder = findIndex(inorder, rootValue);

        // Split the inorder array into left and right subtrees
        vector <int> inorderLeft(inorder.begin(), inorder.begin() + rootIndexInOrder);
        vector <int> inorderRight(inorder.begin() + rootIndexInOrder + 1, inorder.end());

        // The next element in preorder list will be the left child, so skip the root
        // and split the preorder array accordingly
        vector <int>  preorderLeft(preorder.begin()+1, preorder.begin()+1+int(inorderLeft.size()));
        vector <int>  preorderRight(preorder.begin()+1+int(inorderLeft.size()), preorder.end());

        // Recursively construct the left and right subtrees
        root->left = buildTree(preorderLeft, inorderLeft);
        root->right = buildTree(preorderRight, inorderRight);

        return root;
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:


Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Solution

The post in Leetcode gives a nice and clear solutions.

The main idea is similar to the previous question, except for post order traversal, the last element is the root of the tree. Then we can find the index of the root in inorder list. Then we can split the inorder array into left and right subtrees. The next element in postorder list will be the right child, so skip the root and split the postorder array accordingly. Recursively construct the left and right subtrees.

/**
 * 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:
    int findIndex(vector<int>& inorder, int value){
        for (int i = 0; i < inorder.size(); i++){
            if (inorder[i] == value)
                return i;
        }
        return -1;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (empty(postorder))
            return nullptr;
        TreeNode* root = new TreeNode(postorder.back());
        postorder.pop_back();
        int inorderIndex = findIndex(inorder, root->val);
        vector<int> inorderLeft(inorder.begin(), inorder.begin()+inorderIndex);
        vector<int> inorderRight(inorder.begin()+inorderIndex+1, inorder.end());

        vector<int> postorderLeft(postorder.begin(), postorder.begin()+inorderLeft.size());
        vector<int> postorderRight(postorder.begin()+inorderLeft.size(), postorder.end());
        root -> left = buildTree(inorderLeft, postorderLeft);
        root -> right = buildTree(inorderRight, postorderRight);
        return root;
    }
};