第一行为二叉树的中序序列第二行为二叉树的后序序列输出数据一行为二叉树的先序序列C++

#include #include using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

TreeNode* buildTree(vector& inorder, vector& postorder) { int n = inorder.size(); if (n == 0) return NULL;

int rootVal = postorder[n-1];
TreeNode* root = new TreeNode(rootVal);

int rootIndex = 0;
for (int i = 0; i < n; i++) {
    if (inorder[i] == rootVal) {
        rootIndex = i;
        break;
    }
}

vector<int> leftInorder(inorder.begin(), inorder.begin()+rootIndex);
vector<int> rightInorder(inorder.begin()+rootIndex+1, inorder.end());

vector<int> leftPostorder(postorder.begin(), postorder.begin()+rootIndex);
vector<int> rightPostorder(postorder.begin()+rootIndex, postorder.end()-1);

root->left = buildTree(leftInorder, leftPostorder);
root->right = buildTree(rightInorder, rightPostorder);

return root;

}

void preorderTraversal(TreeNode* root) { if (root == NULL) return;

cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);

}

int main() { vector inorder = {9, 3, 15, 20, 7}; vector postorder = {9, 15, 7, 20, 3};

TreeNode* root = buildTree(inorder, postorder);
preorderTraversal(root);

return 0;