题解 | 从中序与后序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树
https://www.nowcoder.com/practice/ab8dde7f01f3440fbbb7993d2411a46b
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ 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(postorder.size()==0) return nullptr; TreeNode*root=new TreeNode(postorder[postorder.size()-1]); for(int i=0;i<inorder.size();i++){ if(root->val==inorder[i]){ vector<int> leftin(inorder.begin(), inorder.begin() + i); vector<int> rightin(postorder.begin(),postorder.begin()+i); // 划分后序遍历的左子树和右子树 vector<int> leftor(inorder.begin()+i+1,inorder.end()); vector<int> rightor(postorder.begin() + i, postorder.end() - 1); root->left=buildTree(leftin,rightin); root->right=buildTree(leftor,rightor); return root; } } return root; } };