Problem: 889. Construct Binary Tree from Preorder and Postorder Traversal 根据前序和后序遍历构造二叉树
前序遍历是【根左右】，后序遍历是【左右根】，所以preorder第一个一定是根节点，postorder最后一个一定是根节点，两者一定相等，postorder倒数第二个一定是右子树的根节点，所以可以根据postorder倒数第二个将前序遍历划分开来，划分成左右子树，前序遍历确定好右子树节点个数以后就可以将后序遍历划分开
Code
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int preL, postL; TreeNode* construct(int preLeft, int preRight, int postLeft, int postRight, vector<int>& preorder, vector<int>& postorder) { if(preLeft > preRight || postLeft > postRight) return nullptr; TreeNode* root = new TreeNode; root->val = preorder[preLeft]; if(preLeft==preRight || postLeft == postRight) return root; int k = preLeft + 1; while(k <= preL && preorder[k]!=postorder[postRight-1]) k++; root->left = construct(preLeft+1, k-1, postLeft, postRight - (preRight - k + 1)-1, preorder, postorder); root->right = construct(k, preRight, postRight - (preRight - k + 1), postRight-1, preorder, postorder); return root; } TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) { TreeNode* root = nullptr; preL = preorder.size()-1; postL = postorder.size()-1; root = construct(0, preL, 0, postL, preorder, postorder); return root; } };
