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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inOrder int整型vector 
     * @param postOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inOrder, vector<int>& postOrder) {
        // write code here
        // 已知中序遍历后后续遍历，重建二叉树;
        if(inOrder.empty() || postOrder.empty())
            return nullptr;
        
        // 从后续遍历的数组中找到根节点
        TreeNode* root = new TreeNode(postOrder.back());
        
        int index = 0;
        for(; index<inOrder.size(); ++index)
        {
            if(inOrder[index]==postOrder.back())
                break;
        }

        cout << index << endl;

        postOrder.pop_back();

        // 如果有节点，则中序遍历和后续遍历的数组都不可能为空，所在index必定在[0,inOrder.size()-1]之间;
        // 左子树的中序遍历
        vector<int> left_inOrder(inOrder.begin(), inOrder.begin()+index);
        // 右子树的中序遍历
        vector<int> right_inOrder(inOrder.begin()+index+1, inOrder.end());

        // 根据根节点在中序遍历中的位置，得到左右子树的“长度”，将后续遍历的数组分为左子树和右子树的后续遍历结果；
        int len = index-0;
        // 左子树的后续遍历
        vector<int> left_postOrder(postOrder.begin(), postOrder.begin()+len);
        // 右子树的后续遍历
        vector<int> right_postOrder(postOrder.begin()+len, postOrder.end());

        root->left = buildTree(left_inOrder, left_postOrder);
        root->right = buildTree(right_inOrder, right_postOrder);

        return root;
    }
};