什么是多页面网站,网络营销优化推广,帝国cms生成网站地图,制作我的第一个网页题目链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
思想#xff1a;
来看一下一共分几步#xff1a; 第一步#xff1a;如果数组大小为零的话#xff0c;说明是空节点了。 第二步#xff1a;如果不为空#xff0c;那么取…题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思想
来看一下一共分几步 第一步如果数组大小为零的话说明是空节点了。 第二步如果不为空那么取后序数组最后一个元素作为节点元素。 第三步找到后序数组最后一个元素在中序数组的位置作为切割点 第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组 第五步切割后序数组切成后序左数组和后序右数组 第六步递归处理左区间和右区间 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;
} 完整代码 class Solution {
private: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;}// 切割中序数组// 左闭右开区间[0, delimiterIndex)vectorint leftInorder(inorder.begin(), inorder.begin() delimiterIndex);// [delimiterIndex 1, end)vectorint rightInorder(inorder.begin() delimiterIndex 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size());// [leftInorder.size(), end)vectorint rightPostorder(postorder.begin() leftInorder.size(), postorder.end());root-left traversal(leftInorder, leftPostorder);root-right traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;return traversal(inorder, postorder);}
};
