如何建立网站的快捷方式,社区自助建站网,南京一对一网站建设,黄石网站设计制作力扣题目链接(opens new window)
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如#xff0c;给出
前序遍历 preorder [3,9,20,15,7] 中序遍历 inorder [9,3,15,20,7] 返回如下的二叉树#xff1a; class Solution {
public:Tr…力扣题目链接(opens new window)
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如给出
前序遍历 preorder [3,9,20,15,7] 中序遍历 inorder [9,3,15,20,7] 返回如下的二叉树 class Solution {
public:TreeNode* dfs(vectorint preorder,int prebeg,int preend,vectorint inorder,int inbeg,int inend){if(prebeg preend) return nullptr;int tmp preorder[prebeg];TreeNode* root new TreeNode(tmp);if(preend - prebeg 1) return root;//切割点int index;for(index inbeg;index inend;index){if(inorder[index] tmp) break;}//切割int leftinbeg inbeg;int leftinend index;int rightinbeg index1;int rightinend inend;int leftprebeg prebeg1;int leftpreend leftprebeg index - inbeg;int rightprebeg leftpreend;int rightpreend preend;root-left dfs(preorder,leftprebeg,leftpreend,inorder,leftinbeg,leftinend);root-right dfs(preorder,rightprebeg,rightpreend,inorder,rightinbeg,rightinend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.size() 0 || inorder.size() 0) return nullptr;return dfs(preorder,0,preorder.size(),inorder,0,inorder.size());}
};
