网站建设 汇卓,网站秒收录工具,友链购买,吉林省水土保持生态建设网站给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]源代码如下… 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]源代码如下
递归
/* 解题思路 1.通过先序遍历的特点我们可以确定地是根节点永远是先序序列的第一个值 2.先分别划分左子树和右子树节点在先序序列和中序序列中的下标范围 3.因为我们要在中序序列中找到根节点的下标所以我们通过哈希表建立中序序列中的节点值和下标的映射关系 //index[inorder[i]]i; 4.在中序遍历中找到根节点的位置后可以确定的是根节点之前的节点都是左子树上的节点根节点之后的节点是右子树上的节点所以我们根据下标关系确认左子树的节点总数leftnode 5.不断更新左子树在先序和中序序列中的左右边界和右子树在先序和中序序列中的左右边界 6.左子树上的所有节点的下标范围先序序列中[preo_left,preo_right] 左子树上的所有节点的下标范围中序序列中[ino_left,ino_right] 7.右子树也是同理 8.递归地构造节点的左子树和右子树 */
class Solution {
public:unordered_mapint,int index;TreeNode* dfs(vectorint preorder, vectorint inorder,int preo_left,int preo_right,int ino_left,int ino_right){if(preo_leftpreo_right) return nullptr;//找到根节点在中序遍历中的下标int in_root_indexindex[preorder[preo_left]];//根节点永远是先序序列的左边界TreeNode* rootnew TreeNode(preorder[preo_left]);//左子树的节点总数为中序序列中根节点的下标-中序遍历的左边界int leftnodein_root_index-ino_left;//注意左右边界的表示root-leftdfs(preorder,inorder,preo_left1,preo_leftleftnode,ino_left,in_root_index-1);root-rightdfs(preorder,inorder,preo_leftleftnode1,preo_right,in_root_index1,ino_right);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int npreorder.size();//建立节点值与下标的映射关系for(int i0;in;i){index[inorder[i]]i;}//初始时边界都为[0,n-1]return dfs(preorder,inorder,0,n-1,0,n-1);}
};
迭代
class Solution {
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.size()0) return nullptr;stackTreeNode* st;TreeNode* rootnew TreeNode(preorder[0]);//根节点是先序遍历的第一值st.push(root);//将根节点入栈int inorder_index0;//中序序列从起始位置开始//开始除根节点之外的其他节点的遍历for(int i1;ipreorder.size();i){int pre_valpreorder[i];TreeNode* nodest.top();//栈顶元素就是根节点//因为在中序序列中根节点将左右子树分开了//所以如果中序序列当前的值不是根节点说明这个值是左子树上的就入栈if(node-val!inorder[inorder_index]){//创建左子树上的节点node-leftnew TreeNode(pre_val);st.push(node-left);}//如果找到根节点了else{//节点出栈直到找到第一个有右子树的根节点while(!st.empty()st.top()-valinorder[inorder_index]){nodest.top();//记录根节点st.pop();//节点出栈inorder_index;//中序序列上的节点不断更新}//找到了就创建右子树上的节点node-rightnew TreeNode(pre_val);st.push(node-right);}}return root;}
};
时间复杂度O(n)
空间复杂度O(n)
