建设网站的网站江苏,旅游网站开发设计与实现,wordpress怎么添加自动推送代码,金华市建设局婺城分局网站106. 从中序与后序遍历序列构造二叉树 - 力扣#xff08;LeetCode#xff09; right要再left前面
如下如#xff0c;后序为第一行#xff0c;最后一个是根#xff1b;
中序为第二行#xff0c;中间的为根#xff1b;
通过后序的最后一个元素从中序中找到根#xff0…106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode right要再left前面
如下如后序为第一行最后一个是根
中序为第二行中间的为根
通过后序的最后一个元素从中序中找到根从而分出左右子树区间 左右子树递归 class Solution {
private:unordered_mapint, int idx_map;int post_idx;public:TreeNode* myBuildTree(int in_left, int in_right, vectorint inorder, vectorint postorder){if (in_left in_right) {return nullptr;}int root_val postorder[post_idx];TreeNode* root new TreeNode(root_val);int index idx_map[root_val];post_idx--;root-right myBuildTree(index 1, in_right, inorder, postorder);root-left myBuildTree(in_left, index-1, inorder, postorder);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {post_idx (int)postorder.size() - 1;int idx 0;for(auto val : inorder){idx_map[val] idx;}return myBuildTree(0, (int)inorder.size() - 1, inorder, postorder);}
};
