网站建设文字表达,wordpress 收购,网站建设百度经验,今天的新闻有哪些输入一棵二叉树前序遍历和中序遍历的结果#xff0c;请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同#xff1b;输入的前序遍历和中序遍历一定合法#xff1b;
数据范围
树中节点数量范围 [0,100]
。
样例
给定#xff1a;
前序遍历是#xff1a;[3, 9, 2…输入一棵二叉树前序遍历和中序遍历的结果请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同输入的前序遍历和中序遍历一定合法
数据范围
树中节点数量范围 [0,100]
。
样例
给定
前序遍历是[3, 9, 20, 15, 7]
中序遍历是[9, 3, 15, 20, 7]返回[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示3/ \9 20/ \15 7代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_mapint,int pos; //用hash表记录每个点在中序遍历的位置vectorint _preorder,_inorder; //动态数组存储前序遍历和中序遍历用于创建树TreeNode* build(int a,int b,int x,int y) //创建数{if(ab) return NULL; //区间为空的时候auto rootnew TreeNode(_preorder[a]); //创建根节点int kpos[root-val]; //子树根节点在中序遍历序列的位置// int k-1,i0;// while(_inorder[i]!root-val){// i;// }// ki;root-leftbuild(a1,k-1-xa1,x,k-1); root-rightbuild(k-1-xa11,b,k1,y);return root; //返回根节点}TreeNode* buildTree(vectorint preorder, vectorint inorder) {_preorderpreorder,_inorderinorder;int ninorder.size();for(int i0;in;i) pos[_inorder[i]]i;return build(0,n-1,0,n-1); //返回递归结果}
};
