力扣每日一题105：从前序与中序序列构造二叉树

本文主要是介绍力扣每日一题105：从前序与中序序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

---

面试中遇到过这道题?

1/5

是

否

通过次数

643.7K

提交次数

899.1K

通过率

71.6%

结点结构

/*** 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* trackback(int l1,int r1,int l2,int r2,vector<int>& preorder,vector<int>& inorder){//参数依次为前序遍历的左、右端点，中序遍历的左、右端点if(l1>r1) return NULL;//找根节点在中序遍历的位置int mid=l2;while(mid<=r2&&inorder[mid]!=preorder[l1])mid++;//构建根节点TreeNode *root=new TreeNode;root->val=preorder[l1];//递归构建右子树int L1,R1,L2,R2;L1=l1+1;R1=l1+mid-l2;L2=l2;R2=mid-1;//cout<<"("<<L1<<","<<R1<<","<<L2<<","<<R2<<")\n";root->left=trackback(L1,R1,L2,R2,preorder,inorder);//递归构建右子树L1=R1+1;R1=r1;L2=mid+1;R2=r2;//cout<<"("<<L1<<","<<R1<<","<<L2<<","<<R2<<")\n";root->right=trackback(L1,R1,L2,R2,preorder,inorder);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();TreeNode *root=trackback(0,n-1,0,n-1,preorder,inorder);return root;}
};

这篇关于力扣每日一题105：从前序与中序序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---