从中序和后续遍历序列构造二叉树
递归法
通过后序的最后找中间点，然后去分割中序，得到左右子树
/** * 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: TreeNode* get_tree(vector<int>& inorder, vector<int>& postorder) { //如果中序数组或者后序数组是空，就返回空节点 if(inorder.size()==0||postorder.size()==0) return nullptr; //后续数组的最后一个是根节点。 TreeNode* root = new TreeNode(postorder[postorder.size()-1]); //根据根节点的值，去找到对应的中序根节点 int root_num ; for(int i= 0 ;i<inorder.size();i++) { if(inorder[i] == root->val) { root_num = i; break; } } //通过中序数组中根节点的位置，根节点前面是左子树，后面是右子树 vector<int> inorder_left(inorder.begin() , inorder.begin()+root_num); vector<int> inorder_right(inorder.begin()+root_num+1 , inorder.end()); //通过中序分割出左子树和右子树的长度，去分割后续数组的左子树和右子树 vector<int> postorder_left(postorder.begin() , postorder.begin() + inorder_left.size()); vector<int> postorder_right(postorder.begin()+ inorder_left.size() , postorder.end()-1); //然后递归迭代，左子树的中序和后续，右子树的中序和后续 root->left = get_tree(inorder_left , postorder_left); root->right = get_tree(inorder_right , postorder_right ); //返归根节点 return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { //如果输入两个数组是空，则返回空节点 if(inorder.size()==0||postorder.size()==0) return nullptr; return get_tree(inorder, postorder); } };
二刷
/** * 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: TreeNode* track_back(vector<int>& inorder, vector<int>& postorder) { if(inorder.size()==0 || postorder.size() == 0) return nullptr; int rootValue = postorder[postorder.size()-1]; TreeNode *root = new TreeNode(rootValue); if(postorder.size()==1 ) return root; int delimiter ; for(delimiter=0 ; delimiter < inorder.size();delimiter++) if(inorder[delimiter] == rootValue) break; vector<int> leftInorder(inorder.begin() , inorder.begin() + delimiter); vector<int> rightInorder(inorder.begin() + delimiter + 1 , inorder.end()); postorder.erase(postorder.end()-1); // postorder.resize(postorder.size()-1); vector<int> leftPostorder(postorder.begin() , postorder.begin() + leftInorder.size()); vector<int> rightPostorder(postorder.begin()+leftInorder.size() , postorder.end()); root->left = track_back(leftInorder,leftPostorder); root->right = track_back(rightInorder,rightPostorder); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(inorder.size()==0 || postorder.size() == 0) return nullptr; TreeNode *root = track_back( inorder ,postorder); return root; } };
