后序中序构造树

约 0 个字 24 行代码

//同前序+中序思路
class Solution {
public:
    unordered_map<int,int> map;
    TreeNode * myTree(vector<int> & inorder ,vector<int>& postorder, int postorder_left,int postorder_right ,int inorder_left,int inorder_right){
        if (postorder_left > postorder_right) return nullptr;
        int postorder_root = postorder_right;
        int inorder_root = map[postorder[postorder_root]];
        TreeNode * root = new TreeNode(postorder[postorder_root]);
        int size_right_tree = inorder_right - inorder_root;
        root->left = myTree(inorder,postorder, postorder_left, postorder_root - 1 - size_right_tree, inorder_left ,inorder_root - 1);
        root->right = myTree(inorder,postorder, postorder_root - size_right_tree , postorder_root - 1,inorder_root + 1,inorder_right);
        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = postorder.size();
        for (int i = 0; i < len; i++){
            map[inorder[i]] = i;
        }
       return  myTree(inorder,postorder, 0, len - 1, 0, len - 1);
    }
};

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

评论区~

有用的话请给我个赞和 star =>
快来跟我聊天~