首页 > 代码库 > Leetcode:Construct Binary Tree 前序和中序、后序和中序构建二叉树
Leetcode:Construct Binary Tree 前序和中序、后序和中序构建二叉树
前序和中序构建二叉树
后序和中序构建二叉树
分析:主要思路就是 在中序中找根节点然后划分左右子树,具体如下:
1. 查找根节点。 我们知道前序序列的第一个元素 和 后序序列的最后一个元素 肯定是根节点,我们就以此为突破口
2. 确定根节点的坐标。 我们在 中序序列中找到 根节点 的下标。
3. 分割左右子树。
对于中序序列:根节点下标之前的都属于左子树,之后的都属于右子树
对于先序序列:根节点之后的 一段元素(该段长度可以由中序序列的左子树长度确定)属于左子树,左子树之后的元素属于右子树
对于先序序列:根节点之前的 一段元素(该段长度可以由中序序列的右子树长度确定)属于右子树,右子树之后的元素属于左子树
4.对分割好的左右子树递归构建二叉树,注意确定好每段序列的下标范围
例如:
preorder = {7,10,4,3,1,2,8,11} inorder = {4,10,3,1,7,11,8,2}
第一步:查找根节点,对于先序而言,根节点就是第一个元素,也就是7
第二步:确定根节点的坐标,我们在 中序中查找根节点7,确定下标为4
第三步:分割左右子树。
对于中序序列:左子树为 {4, 10, 3, 1}, 右子树为{11, 8, 2}
对于先序序列:左子树为 {10, 4, 3, 1}, 右子树为{2, 8, 11}
注意:任何时候中序序列和先序序列的长度总是相等的。
class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { return constructTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } TreeNode* constructTree(const vector<int>& preorder, int preFirst, int preLast, const vector<int>& inorder, int inFirst, int inLast) { int preLen = preLast - preFirst + 1; int inLen = inLast - inFirst + 1; assert(preLen == inLen && preLen >= 0); if (preLen == 0) return nullptr; TreeNode* root = new TreeNode(preorder.at(preFirst)); int rootIndex = distance(inorder.begin(), find(inorder.begin(), inorder.end(), preorder.at(preFirst))); int leftLen = rootIndex - inFirst; int rightLen = inLast - rootIndex; root->left = constructTree(preorder, preFirst + 1, preFirst + leftLen, inorder, inFirst, rootIndex - 1); root->right = constructTree(preorder, preLast - rightLen + 1, preLast, inorder, rootIndex + 1, inLast); return root; } };
class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { return constructTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1); } TreeNode* constructTree(const vector<int>& inorder, int inFirst, int inLast, const vector<int>& postorder, int postFirst, int postLast) { int postLen = postLast - postFirst + 1; int inLen = inLast - inFirst + 1; assert(postLen == inLen && postLen >= 0); if (postLen == 0) return nullptr; TreeNode* root = new TreeNode(postorder.at(postLast)); int rootIndex = distance(inorder.begin(), find(inorder.begin(), inorder.end(), postorder.at(postLast))); int leftLen = rootIndex - inFirst; int rightLen = inLast - rootIndex; root->left = constructTree(inorder, inFirst, rootIndex - 1, postorder, postFirst, postFirst + leftLen - 1); root->right = constructTree(inorder, rootIndex + 1, inLast, postorder, postLast - rightLen, postLast - 1); return root; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。