做网站用jsp和html,软件开发培训班,百度搜索引擎收录入口,新网 搭建wordpress从前序遍历与中序遍历序列构造二叉树 前序遍历#xff1a;中左右 中序遍历#xff1a;左中右 前序遍历的第一个数必定为根节点#xff0c;再到中序遍历中找到该数#xff0c;数的左边是左子树#xff0c;右边是右子树#xff0c;进行递归即可。
#includevector…从前序遍历与中序遍历序列构造二叉树 前序遍历中左右 中序遍历左中右 前序遍历的第一个数必定为根节点再到中序遍历中找到该数数的左边是左子树右边是右子树进行递归即可。
#includevector
using namespace std;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 {
private:TreeNode* build(vectorint preorder, vectorint inorder){if (preorder.size() 0)return NULL;//找到根节点int rootvalue preorder[0];TreeNode* root new TreeNode(rootvalue);//叶子节点if (preorder.size() 1)return root;//区分左右子树位置int index 0;for (int i 0;i inorder.size();i){if (inorder[i] rootvalue){index i;break;}}vectorintleft_in(inorder.begin(), inorder.begin() index);vectorintright_in(inorder.begin() index 1, inorder.end());vectorintleft_pre(preorder.begin() 1, preorder.begin() 1 left_in.size());vectorintright_pre(preorder.begin() 1 left_in.size(), preorder.end());root-left build(left_pre, left_in);root-right build(right_pre, right_in);return root;}
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {return build(preorder, inorder);}
};int main()
{vectorint preorder { 3,9,20,15,7 };vectorint inorder { 9,3,15,20,7 };Solution solution;TreeNode* rootsolution.buildTree(preorder, inorder);
}
