做图素材网站开通会员哪个好,做网站一年赚几百万,网上商城购物系统论文,网站打开慢的解决方法从前序遍历与中序遍历序列构造二叉树 前序遍历#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);
}
