题解 | #牛群的树形结构重建#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <sys/types.h>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inOrder int整型vector 
     * @param postOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* build(vector<int>& inOrder, int l1, int r1, vector<int>& postOrder, int l2, int r2) {
        if (l1 > r1) return nullptr;
        TreeNode* root = new TreeNode(postOrder[r2]);
        // 找到切分左右的位置
        int index;
        for (int i = l1; i <= r1; i++) {
            if (inOrder[i] == postOrder[r2]) {
                index = i;
                break;
            }
        }
        // 左树的元素索引位置为l1=>index-1,对应后续遍历的数组中，根据长度来确定起止位置l2=>l2+(index-l1-1)，其中(index-l1-1)表示的是元素的个数，即为长度
        root->left = build(inOrder, l1, index-1, postOrder, l2, l2+index-l1-1);
        // 右树的起止位置为index+1=>r1，对应后续数组中的起止位置为l2+index-l1=>r2-1
        root->right = build(inOrder, index+1, r1, postOrder, l2+index-l1, r2-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        // write code here
        int l1 = 0, r1 = inOrder.size()-1;
        int l2 = 0, r2 = postOrder.size()-1;
        return build(inOrder, l1, r1, postOrder, l2, r2);
    }
};