Very intuitive recursive solution in cpp


  • 1

    Just using p_l and p_h for lower and upper index in vector preorder while the same logic applied in inorder to split the vector up and up till the end, a typical DFS recursive problem.


    class Solution {
    private:
        TreeNode* buildTree(const vector<int>& preorder, int p_l, int p_h, const vector<int>& inorder, int i_l, int i_h)
        {
            if(i_l > i_h) return NULL;
            int val = preorder[p_l];
            TreeNode *root = new TreeNode(val);
            int i = i_l;
            for(; i <= i_h; i++)
                if(inorder[i] == val) break;
            root->left = buildTree(preorder, p_l+1, p_l+i-i_l, inorder, i_l, i-1);
            root->right = buildTree(preorder, p_l+i-i_l+1, p_h, inorder, i+1, i_h);
            return root;
        }
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
        }
    };

  • 0

    Construct Binary Tree from Inorder and Postorder Traversal should be enclosed here.


    class Solution {
    private:
        TreeNode* buildTree(const vector<int>& inorder, int i_l, int i_h, const vector<int>& postorder, int p_l, int p_h)
        {
            if(i_l > i_h) return NULL;
            int val = postorder[p_h];
            TreeNode *root = new TreeNode(val);
            int i = i_l;
            for(; i <= i_h; i++)
                if(inorder[i] == val) break;
            root->left = buildTree(inorder, i_l, i-1, postorder, p_l, p_l+i-i_l-1);
            root->right = buildTree(inorder, i+1, i_h, postorder, p_l+i-i_l, p_h-1);
            return root;
        }
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            return buildTree(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.