思路很容易想,但是能不能顺利写出代码来又是另外一回事。

一共提交了16次才成功,我的妈啊。。。

为了加快编码速度,防止出错,加点小总结:

  • TreeNode* inOrder(vector<int> &inorder, int inL, int inR, vector<int> &postorder, int pL, int pR)TreeNode* inOrder(vector<int> &inorder, vector<int> &postorder, int inL, int inR, int pL, int pR)
  • 使用闭区间比使用开区间好
  • 时刻注意区间范围,不要老想着区间是0~size-1
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param inorder int整型vector
     * @param postorder int整型vector
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        int size = inorder.size();
        if (size < 1) return nullptr;
        return inOrder(inorder, 0, size-1, postorder, 0, size-1);
    }

    TreeNode* inOrder(vector<int> &inorder, int inL, int inR,
                      vector<int> &postorder, int pL, int pR){
        if (inL > inR) return nullptr;
        TreeNode *root = new TreeNode(postorder[pR]);
        int mid = inL;
        for (; mid <= inR; ++mid)
            if (inorder[mid] == root->val) break;
        int leftSize = mid - inL;
        // 左中右 左右中
        root->left = inOrder(inorder, inL, mid-1, postorder, pL, pL+leftSize-1);
        root->right = inOrder(inorder, mid+1, inR, postorder, pL+leftSize, pR-1);
        return root;
    }
};