二叉树的构造：从中序和后序序列构造二叉树（前序遍历）

中 + 后构造二叉树

一层层切割，故想到递归

如果数组大小为0，说明是空结点了
如果不为空，则去后序数组最后一个元素作为节点元素
找到后序数组最后一个元素在中序数组的位置，作为切割点
切割中序数组，切割为中序左数组和中序右数组（一定是先切割中序数组）
切割后序数组，切为后序左数组和后序右数组
递归处理左区间和右区间

中序数组大小一定是和后序数组的大小相同的（这是必然）。
故可以根据切好的中序来分割后序

class Solution {
public:
//inorder.size() == postorder.size()
    TreeNode* traverse(vector& inorder, vector& postorder){
        //有可能上一层postorder.size() = 2, 从而一边有孩子，一边没有孩子
        if(postorder.size() == 0) return NULL;//空结点？

        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        //叶子结点
        if(postorder.size() == 1) return root;

        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++){
            if(inorder[delimiterIndex] == rootValue)
                break;
        } 
        //切割中序数组
        //左闭右开，长度为右index-左index 
        //[0, delimiterIndex)
        vector leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        vector rightInoder(inorder.begin() + delimiterIndex + 1, inorder.end());

        //remove the last element
        postorder.resize(postorder.size() - 1);

        //切割后序数组
        vector leftPost(postorder.begin(), postorder.begin() + leftInorder.size());
        vector rightPost(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traverse(leftInorder, leftPost);
        root->right = traverse(rightInoder, rightPost);

        return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0)
        return NULL;

        return traverse(inorder, postorder);
    }
};

如上的代码性能并不好，应为每层递归定定义了新的vector（就是数组），既耗时又耗空间，但上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。

下面给出用下表索引写出的代码版本：（思路是一样的，只不过不用重复定义vector了，每次用下表索引来分割）

class Solution {
private:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector& inorder, int inorderBegin, int inorderEnd, vector& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

最终简化版

class Solution {
private:
    // 中序区间：[b1, e1)，后序区间[b2, e2)
    TreeNode* traversal (vector& inorder, int b1, int e1, vector& postorder, int b2, int e2) {
        if(e2 == b2) return NULL;

        int midValue = postorder[e2 - 1];
        TreeNode* root = new TreeNode(midValue);

        if(e2 - b2 == 1) return root;

        int delimiter;
        for(delimiter = b1; delimiter < e1; delimiter++){
            if(inorder[delimiter] == midValue) break;
        }

        root->left = traversal(inorder, b1, delimiter, postorder, b2, b2 + delimiter - b1);
        root->right = traversal(inorder, delimiter + 1, e1, postorder, b2 + delimiter - b1 , e2-1);

        return root;

    }
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

中+前构造二叉树：
和后+中道理一样

class Solution {
public:
    TreeNode* traversal(vector& preorder, int b1, int e1, vector& inorder, int b2, int e2){
        if(e2 == b2) return NULL;

        int midValue = preorder[b1];
        TreeNode* root = new TreeNode(midValue);

        if(e2 - b2 == 1) return root;

        int dilimiter;
        for(dilimiter = b2; dilimiter < e2; dilimiter++){
            if(inorder[dilimiter] == midValue) break;
        }


        root->left = traversal(preorder, b1 + 1, b1 + 1 + (dilimiter - b2), inorder, b2, dilimiter);
        root->right = traversal(preorder, b1 + 1 + (dilimiter - b2), e1, inorder, dilimiter + 1, e2);

        return root;
    }

    TreeNode* buildTree(vector& preorder, vector& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0)
            return NULL;
        
        return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};

思路和上面两题思路一样

构造二叉树一般都是前序遍历，因为得先构造中间结点，然后再递归构造左子树和右子树

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector& nums) {
        if(nums.size() == 0) return NULL;

        int maxValue = -1;
        int maxIndex;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }

        TreeNode* root = new TreeNode(maxValue);

        if(nums.size() == 1) return root;
        //左闭右开
        vector leftNums(nums.begin(), nums.begin() + maxIndex);
        //左闭右开
        vector rightNums(nums.begin() + maxIndex + 1, nums.end());

        root->left = constructMaximumBinaryTree(leftNums);
        root->right = constructMaximumBinaryTree(rightNums);

        return root;

    }
};

因为每次都要构造新的vector，所以效率不高，可以使用下标索引的方法来直接在原数组上构造二叉树
注意易错点：

class Solution {
public:
    TreeNode* constructBinaryTree(vector& nums, int start, int end) {
        if(start == end) return NULL; //**易错

        int maxValue = -1;
        int maxIndex;
        for(int i = start; i < end; i++){ //*易错
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }

        TreeNode* root = new TreeNode(maxValue);

        if(end - start == 1) return root; //易错
        

        root->left = constructBinaryTree(nums, start, maxIndex); 易错
        root->right = constructBinaryTree(nums, maxIndex + 1, end); //易错

        return root;

    }

    TreeNode* constructMaximumBinaryTree(vector& nums){
        return constructBinaryTree(nums, 0, nums.size());
    }
};

前序遍历：（自己）

内存耗费很高因为构造了一颗新树，每次都要构造一个新结点

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return NULL;

        int midValue;
        TreeNode* root = new TreeNode(0);
        if(root2 && root1){
            midValue = root1->val + root2->val;
            
            root->val = midValue;
            root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
        } 
        else if(root1 && !root2){
            midValue = root1->val;
            
            root->val = midValue;
            root->left = mergeTrees(root1->left, NULL);
            root->right = mergeTrees(root1->right, NULL);
            
        } 
        else if(!root1 && root2){
            midValue = root2->val;
            
            root->val = midValue;
            root->left = mergeTrees(NULL, root2->left);
            root->right = mergeTrees(NULL,root2->right);
            
        }

        

        return root;
    }
};

改进：
以root1为基础构造新树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2;
        if(!root2) return root1;

        root1->val += root2->val;

        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;

    }
};

这题前中后都行

二叉树的构造：从中序和后序序列构造二叉树（前序遍历）

C/C++/C#相关栏目本月热门文章