深圳网站建设哪家公司好,网页设计与网站开发什么区别,南海做网站公司,网站开发完成后如何发布一、题目 二、思路及代码 前序遍历#xff1a;中、左、右。所以前序遍历的第一个节点是树的根节点#xff0c;第二个节点是左子树的根节点。。。。 中序遍历#xff1a;左、中、右。树的根节点在中间某处 我们可以根据二者的特点结合一下#xff1a;对于前序遍历序列{1,2,4…一、题目 二、思路及代码 前序遍历中、左、右。所以前序遍历的第一个节点是树的根节点第二个节点是左子树的根节点。。。。 中序遍历左、中、右。树的根节点在中间某处 我们可以根据二者的特点结合一下对于前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} 根据前序可知1是树的根节点那么再看中序就可以用1分成左子树{4,7,2}和右子树{5,3,8,6}。再看前序的第二个元素是2,2就是左子树的根节点于是{4,7}是2的左子树2没有右子树。 …以此类推就可以得到一颗完整的树。 那么根据上面的分析我们可以把判断过程分成3步
读取前序的第一个元素根据这个元素将中序数组拆分成左子树、根节点、右子树左、右子树各自重复上边的步骤组成自己的二叉树创建一个根节点左右指针分别指向第二步得到的子树节点 显然每一个节点都可以使用上述步骤那么我们就可以把这个过程写成递归。
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param preOrder int整型vector * param vinOrder int整型vector * return TreeNode类*/TreeNode* reConstructBinaryTree(vectorint preOrder, vectorint vinOrder) {// write code here//若数组为空则说明已经没有新的节点了返回空if(vinOrder.size()0){return NULL;} vectorint lefttree;vectorint righttree;int i0;//获取左子树数组for(i;ivinOrder.size();i){if(vinOrder[i]preOrder[0]){break;}else{lefttree.push_back(vinOrder[i]);}}//这里把用过的第一个节点删除掉那么递归过程就可以一直使用preOrder[0]获取当前根节点preOrder.erase(preOrder.begin()); //删除掉第一个元素TreeNode *leftreConstructBinaryTree(preOrder, lefttree);//获取右子树数组for(int ji1;jvinOrder.size();j){righttree.push_back(vinOrder[j]);}TreeNode *rightreConstructBinaryTree(preOrder, righttree);//当前根节点TreeNode *rootnew TreeNode(vinOrder[i]); root-leftleft;root-rightright;return root;}
};
