用v9做网站优化,发布网站需要备案,全国建筑企业资质查询平台下载,wordpress网站映射1.题目解析 题目来源#xff1a;105.从前序与中序遍历序列构造二叉树——力扣 测试用例 2.算法原理 首先要了解一个概念 前序遍历#xff1a;按照 根节点-左子树-右子树的顺序遍历二叉树 中序遍历#xff1a;按照 左子树-根节点-右子树的顺序遍历二叉树 题目… 1.题目解析 题目来源105.从前序与中序遍历序列构造二叉树——力扣 测试用例 2.算法原理 首先要了解一个概念 前序遍历按照 根节点-左子树-右子树的顺序遍历二叉树 中序遍历按照 左子树-根节点-右子树的顺序遍历二叉树 题目中我们可知需要根据给出的前序遍历序列与中序遍历序列构建一个二叉树解题思路就是通过前序序列确定根节点然后根据找出的根节点将中序序列分为:[左子树根节点右子树]这样三个范围然后递归构造左子树与右子树以此类推直到完成构建 3.实战代码 /*** Definition for a binary tree node.* 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 {
public:TreeNode* build(vectorint preorder, vectorint inorder,int previ,int inbegin,int inend){if(inbegin inend){return nullptr;}//创建根节点TreeNode* root new TreeNode(preorder[previ]);//通过前序确定根节点后将中序数组分为三部分//左子树 根节点 右子树int rooti inbegin;while(inbegin inbegin){if(inorder[rooti] preorder[previ]){break;}//寻找中序中的根节点所在的的位置rooti;}//此时前序中的根节点构建完成向后构建其他子树的根节点previ;//左子树递归构建[inbegin,rooti-1]区间//右子树递归构建[root1,inend]区间root-left build(preorder,inorder,previ,inbegin,rooti-1);root-right build(preorder,inorder,previ,rooti1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;return build(preorder,inorder,i,0,preorder.size()-1);}
};
