根据后序数组的最后一位把中序分成左右两个。那么代码应该怎么写呢说到一层一层切割就应该想到了递归。第一步如果数组大小为零的话说明是空节点了。第二步如果不为空那么取后序数组最后一个元素作为节点元素。第三步找到后序数组最后一个元素在中序数组的位置作为切割点第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组第五步切割后序数组切成后序左数组和后序右数组第六步递归处理左区间和右区间TreeNode* traversal (vectorint inorder, vectorint postorder) { // 第一步 if (postorder.size() 0) return NULL; // 第二步后序遍历数组最后一个元素就是当前的中间节点 int rootValue postorder[postorder.size() - 1]; TreeNode* root new TreeNode(rootValue); // 叶子节点 if (postorder.size() 1) return root; // 第三步找切割点 int delimiterIndex; for (delimiterIndex 0; delimiterIndex inorder.size(); delimiterIndex) { if (inorder[delimiterIndex] rootValue) break; } // 第四步切割中序数组得到 中序左数组和中序右数组 // 第五步切割后序数组得到 后序左数组和后序右数组 // 第六步 root-left traversal(中序左数组, 后序左数组); root-right traversal(中序右数组, 后序右数组); return root; }这是完整代码我把要注意的地方都标注进去了/** * 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* traversal(vectorint inorder, vectorint postorder){ if(postorder.size()0)return NULL; int rootvaluepostorder[postorder.size()-1]; TreeNode*rootnew TreeNode(rootvalue); if(postorder.size()1)return root; //不要忘记这一步接下来先找切割点 int delimiterIndex; for(delimiterIndex0;delimiterIndexinorder.size();delimiterIndex){ if(inorder[delimiterIndex]rootvalue)break; } //接下来分割中序,得到中序左中序右 vectorintinorderleft(inorder.begin(),inorder.begin()delimiterIndex);//代码中我坚持左闭右开的原则 vectorintinorderright(inorder.begin()delimiterIndex1,inorder.end());//不要忘了加1跳过root。C 里的 end() 是“最后一个元素的下一个位置”所以左闭右开最后一个也存上了 //分割后续得到后续左后续右 postorder.pop_back(); vectorintpostorderleft(postorder.begin(),postorder.begin()delimiterIndex); vectorintpostorderright(postorder.begin()delimiterIndex,postorder.end()); root-lefttraversal(inorderleft,postorderleft); root-righttraversal(inorderright,postorderright); return root; } TreeNode* buildTree(vectorint inorder, vectorint postorder) { return traversal(inorder,postorder); } };为什么vectorintinorderleft(inorder.begin(),inorder.begin()delimiterIndex);是左闭右开的这行代码是怎么执行“左闭右开”的当你写下vectorint inorderleft(inorder.begin(), inorder.begin() delimiterIndex);编译器会这样操作起点左闭从inorder.begin()指向的位置开始即数组的第一个元素索引 0包含它。终点右开向后移动一直移动到inorder.begin() delimiterIndex指向的位置即索引delimiterIndex。停止条件一旦到达终点位置立即停下来不拷贝终点位置指向的那个元素。在后序数组里delimiterIndex是“左子树的个数”后序的结构是[左子树全部] [右子树全部] [根节点]。我们先把根节点pop_back()扔掉了剩下[左子树全部] [右子树全部]。现在问题来了左子树有几个节点答案就是delimiterIndex个因为中序里左子树有delimiterIndex个整棵树节点总数是守恒的。此时写postorder.begin() delimiterIndex起点是begin终点是begin 左子树个数。这个区间取了[0, 左子树个数)也就是刚刚好取了全部左子树节点。这里并没有“根节点”需要跳过因为根节点已经被我们提前扔掉了。所以不需要加 1。中序[9, 3, 15, 20, 7]后序[9, 15, 7, 20, 3]根 3delimiterIndex 1左子树有 1 个节点9看后序切割去掉根postorder变为[9, 15, 7, 20]长度 4。左后序取前 1 个postorder.begin() 1指向数字15。区间[begin, begin1)只取了索引 0数字9。结果[9]✅ 一个不多一个不少右后序取剩下的begin 1到end取了[15, 7, 20]✅ 正确接下来用一个前中数组检测一下自己学会了没有/** * 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* build(vectorint preorder, vectorint inorder) { if(preorder.size()0)return NULL; int rootvaluepreorder[0];//这里不要写成1了 TreeNode*rootnew TreeNode(rootvalue); //返回根节点。 if(preorder.size()1)return root; //找断点 int delimiterIndex; for(delimiterIndex0;delimiterIndexinorder.size();delimiterIndex){ if(inorder[delimiterIndex]rootvalue)break; } //左闭右开分中序遍历 vectorintleftin(inorder.begin(),inorder.begin()delimiterIndex); vectorintrightin(inorder.begin()delimiterIndex1,inorder.end()); //分前序遍历前先去掉第一位。 preorder.erase(preorder.begin()); //开始分割 vectorintleftpre(preorder.begin(),preorder.begin()delimiterIndex); vectorintrightpre(preorder.begin()delimiterIndex,preorder.end()); //开始递归 root-leftbuild(leftpre,leftin); root-rightbuild(rightpre,rightin); return root; } TreeNode* buildTree(vectorint preorder, vectorint inorder) { return build(preorder,inorder); } };
