合肥做淘宝网站,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);
}
