题解 | #从中序与后序遍历序列构造二叉树#

#include <vector>
class Solution {
public:
	//根据101的BM40写出的解法
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
	  	// n == m 这样写逻辑比较易懂
        int n = inorder.size();
        int m = postorder.size();

        if(n == 0 || m == 0){
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[m-1]);
        for(int i = 0; i < n; i++){
            if(postorder[m-1] == inorder[i]) {
                vector<int> leftin(inorder.begin(), inorder.begin() + i);
                vector<int> leftpost(postorder.begin(), postorder.begin() + i);
                root->left = buildTree(leftin, leftpost);

                vector<int> rightin(inorder.begin()+i+1, inorder.end());
                vector<int> rightpost(postorder.begin() + i, postorder.end() - 1);
                root->right = buildTree(rightin, rightpost);
                break;
            }
        }
        return root;
    }
};